Hamiltonian colorings of graphs with long cycles
Ladislav Nebeský · Mathematica Bohemica · 2003
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$.