Hamiltonian colorings of graphs

AbstractFor vertices u and v in a connected graph G of order n, the length of a longest u–v path in G is denoted by D(u,v). A hamiltonian coloring c of G is an assignment c of colors (positive integers) to the vertices of G such that D(u,v)+|c(u)-c(v)|⩾n-1 for every two distinct vertices u and v of G. The value hc(c) of a hamiltonian coloring c of G is the maximum color assigned to a vertex of G. The hamiltonian chromatic number hc(G) of G is min{hc(c)} over all hamiltonian colorings c of G. Hamiltonian chromatic numbers of some special classes of graphs are determined. It is shown that for every two integers k and n with k⩾1 and n⩾3, there exists a hamiltonian graph of order n with hamiltonian chromatic number k if and only if 1⩽k⩽n-2. Also, a sharp upper bound for the hamiltonian chromatic number of a connected graph in terms of its order is established