On hamiltonian colorings of block graphs
arXiv:1609.02871 · doi:10.1007/978-3-319-30139-6_3
Abstract
A hamiltonian coloring c of a graph G of order p is an assignment of colors to the vertices of G such that for every two distinct vertices u and v of G, where D(u,v) denoted 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.
12 pages, 1 figure. A conference version appeared in the proceedings of WALCOM 2016