On Hamiltonian Colorings For Some Graphs

Let G be a connected graph of order n. For every two distinct vertices u and v, let D(u,v) denote the length of a longest u-v path in G. A hamiltonian coloring of a connected graph G of order n, is an assignment c of colors(positive integers) to the vertices in G such that D(u,v)+|c(u)-c(v)|≥n-1 for every two distinct vertices u and v in G. The value hc(c) of a hamiltonian coloring c is maximum color assigned to a vertex of G. The hamiltonian chromatic number hc(G) of G is min hc(c) taken over all hamiltonian colorings c of G.In recent years, as a hot topic of the graph theory, the hamiltonian colorings of graphs have been researched extensively and widely, Hamiltonian chromatic numbers of some special classes of graphs are determined, in this paper, we discuss the hamiltonian chromatic number of a class of caterpillars, and determine the hamiltonian chromatic number.