The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs
Ladislav Nebeský · Czechoslovak Mathematical Journal · 2006
If G is a connected graph of order n ⩾ 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 |c(x) − c(y)| ⩾ 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 ∈ 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 ⩾ 3. Assume that there exists a subgraph F of G such that F is a hamiltonian-connected graph of order i, where 2 ⩽ i ⩽ 1/2 (n+1). Then hc(G) ⩽ (n−2)2+1−2(i−1)(i−2).