On hamiltonian colorings of graphs

AbstractA hamiltonian coloring of a connected graph G of order n is an assignment c of colors (positive integers) to the vertices of G such that |c(u)-c(v)|+D(u,v)⩾n-1 for every two distinct vertices u and v of G, where D(u,v) is the length of a longest u–v path in G. For a hamiltonian coloring c, hc(c) is the largest color assigned to a vertex of G; while the hamiltonian chromatic number hc(G)=min{hc(c)} over all hamiltonian colorings c of G. The circumference cir(G) of a graph G is the length of a longest cycle in G. A lower bound for cir(G) is given in terms of the number of vertices that receive colors between two specified colors in a hamiltonian coloring of G. As a consequence of this result, it follows that if there exists a hamiltonian coloring of a connected graph G of order n⩾3 such that at least (n+2)/2 vertices of G are colored the same, then G is hamiltonian. Also, if there exists a hamiltonian coloring of a connected graph G of order n⩾4 such that at least (n+2)/2 vertices of G are colored with one of two consecutive colors, then cir(G)⩾n-1. Furthermore, it is shown that if G is a connected graph of order n⩾4 with 2⩽hc(G)⩽n-1, then cir(G)⩾n+2-hc(G). Moreover, if G is a connected graph of order n⩾5 that is not a star, then hc(G)⩽(n-2)2-1