On Hamiltonian Colorings of Block Graphs
A hamiltonian coloring c of a graph G of order p is an assignment of colors to the vertices of G such that D(u, v) |c(u) c(v) \ge (p 1\ for every two distinct vertices u and v of G, where D(u, v) denotes the detour distance between u and v. The value hc(c) of a hamiltonian coloring c is the maximum color assigned to a vertex of G. The hamiltonian chromatic number, denoted by hc(G) is the min{hc(c) taken over all hamiltonian coloring c of G. In this paper, we present a lower bound for the hamiltonian chromatic number of block graphs and give a sufficient condition to achieve the lower bound. We characterize symmetric block graphs achieving this lower bound. We present two algorithms for optimal hamiltonian coloring of symmetric block graphs.
WALCOM