×
Chartrand, Gary; Nebeský, Ladislav; Zhang, Ping

On Hamiltonian colorings of graphs. (English) Zbl 1059.05046

Discrete Math. 290, No. 2-3, 133-143 (2005).
The authors give a lower bound for the circumference of a graph in terms of the number of vertices that receive colors between two specified colors in a Hamiltonian coloring of the graph. As a consequence, if there exists a Hamiltonian coloring of a connected graph \(G\) of order \(n\) such that at least \((n+2)/2\) vertices of \(G\) are colored with one of two consecutive colors, then the circumference of \(G\) is at least \(n-1\).
Reviewer: Hang Tong Lau (Montréal)

Cited in 4 Documents

MSC:

05C15 Coloring of graphs and hypergraphs
05C12 Distance in graphs
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)

Keywords:

Hamiltonian colorings; Hamiltonian-connected graphs; circumference
PDF BibTeX XML Cite
\textit{G. Chartrand} et al., Discrete Math. 290, No. 2--3, 133--143 (2005; Zbl 1059.05046)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Bondy, J.A.; Chvátal, V., A method in graph theory, Discrete math., 15, 111-136, (1976) · Zbl 0331.05138
[2] Chartrand, G.; Erwin, D.; Harary, F.; Zhang, P., Radio labelings of graphs, Bull. inst. combin. appl., 33, 77-85, (2001) · Zbl 0989.05102
[3] Chartrand, G.; Erwin, D.; Zhang, P., Radio antipodal colorings of graphs, Math. bohem., 127, 57-69, (2002) · Zbl 0995.05056
[4] G. Chartrand, D. Erwin, P. Zhang, A graph labeling problem suggested by FM channel restrictions, Bull. Inst. Combin. Appl., to appear. · Zbl 1066.05125
[5] Chartrand, G.; Nebeský, L.; Zhang, P., Greedy \(F\)-colorings of graphs, Discrete math., 272, 37-46, (2003) · Zbl 1029.05048
[6] Chartrand, G.; Nebeský, L.; Zhang, P., Radio \(k\)-colorings of paths, Discuss. math. graph theory, 24, 5-21, (2004) · Zbl 1056.05053
[7] Chartrand, G.; Nebeský, L.; Zhang, P., Hamiltonian colorings of graphs, Discrete appl. math., 146, 246-261, (2005)
[8] Fotakis, D.; Pantziou, G.; Pentaris, G.; Spirakis, P., Frequency assignment in mobile and radio networks, DIMACS ser. discrete math. theoret. comput. sci., 45, 73-90, (1999) · Zbl 0929.68005
[9] Hale, W., Frequency assignmenttheory and applications, Proc. IEEE, 68, 1497-1514, (1980)
[10] van den Heuvel, J.; Leese, R.A.; Shepherd, M.A., Graph labeling and radio channel assignment, J. graph theory, 29, 263-283, (1998) · Zbl 0930.05087
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.