# Article

Full entry | PDF   (0.3 MB)
Keywords:
connected graphs; hamiltonian colorings; circumference
Summary:
By a hamiltonian coloring of a connected graph $G$ of order $n \ge 1$ we mean a mapping $c$ of $V(G)$ into the set of all positive integers such that $\vert c(x) - c(y)\vert \ge n - 1 - D_G(x, y)$ (where $D_G(x, y)$ denotes the length of a longest $x-y$ path in $G$) for all distinct $x, y \in G$. In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order $n \ge 5$ with circumference $n - 2$.
References:
[1] G. Chartrand, L. Lesniak: Graphs & Digraphs. Third edition. Chapman and Hall, London, 1996. MR 1408678
[2] G. Chartrand, L. Nebeský, P. Zhang: Hamiltonian colorings of graphs. Preprint (2001). MR 2115148
[3] G. Chartrand, L. Nebeský, P. Zhang: On hamiltonian colorings of graphs. Preprint (2001). MR 2115148

Partner of