By a hamiltonian coloring of a connected graph G of order n ≥ 1 we mean a mapping c of V (G) into the set of all positive integers such that |c(x) − c(y)| ≥ n − 1 − DG(x, y) (where DG(x, y) denotes the length of a longest x − y path in G) for all distinct x, y ∈ G. In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order n ≥ 5 with circumference n − 2.
If $G$ is a connected graph with distance function $d$, then by a step in $G$ is meant an ordered triple $(u, x, v)$ of vertices of $G$ such that $d(u, x) = 1$ and $d(u, v) = d(x, v) + 1$. A characterization of the set of all steps in a connected graph was published by the present author in 1997. In Section 1 of this paper, a new and shorter proof of that characterization is presented. A stronger result for a certain type of connected graphs is proved in Section 2.
If $G$ is a connected graph of order $n \ge 1$, then by a hamiltonian coloring of $G$ 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 V(G)$. Let $G$ be a connected graph. By the hamiltonian chromatic number of $G$ we mean \[ \min (\max (c(z);\, z \in V(G))), \] where the minimum is taken over all hamiltonian colorings $c$ of $G$. The main result of this paper can be formulated as follows: Let $G$ be a connected graph of order $n \ge 3$. Assume that there exists a subgraph $F$ of $G$ such that $F$ is a hamiltonian-connected graph of order $i$, where $2 \le i \le \frac{1}{2}(n + 1)$. Then $\mathop {\mathrm hc}(G) \le (n - 2)^2 + 1 - 2(i - 1)(i - 2)$.