On hamiltonian colorings for some graphs

For a connected graph GG and any two vertices uu and vv in GG, let D(u,v)D(u,v) denote the length of a longest u–vu–v path in GG. A hamiltonian coloring of a connected graph GG of order nn is an assignment cc of colors (positive integers) to the vertices of GG such that |c(u)−c(v)|+D(u,v)≥n−1|c(u)−c(v)|+D(u,v)≥n−1 for every two distinct vertices uu and vv in GG. The value  hc(c) of a hamiltonian coloring cc is the maximum color assigned to a vertex of GG. The hamiltonian chromatic number  hc(G) of GG is min{hc(c)} taken over all hamiltonian colorings cc of GG. In this paper we discuss the hamiltonian chromatic number of graphs GG with max{D(u,v)|u,v∈V(G),u≠v}≤n2. As examples, we determine the hamiltonian chromatic number for a class of caterpillars, and double stars.