Hamiltonian chromatic number of block graphs

Devsi Bantva

Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation (WALCOM 2016) , Tome 21 (2017) no. 3, pp. 353-369.

Résumé

Let $G$ be a simple connected graph of order $n$. A hamiltonian coloring $c$ of a graph $G$ is an assignment of colors (non-negative integers) to the vertices of $G$ such that $D(u, v)$ + $|c(u) - c(v)|$ $\geq$ $n - 1$ for every two distinct vertices $u$ and $v$ of $G$, where $D(u, v)$ denotes the detour distance between $u$ and $v$ in $G$ which is the length of the longest path 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 $\min\{hc(c)\}$ taken over all hamiltonian coloring $c$ of $G$. In this paper, we give a necessary and sufficient condition to achieve a lower bound for the hamiltonian chromatic number of block graphs given in [Bantva, WALCOM 2016. Theorem 1]. We present an algorithm for optimal hamiltonian coloring of a special class of block graphs, namely $SDB(p/2)$ block graphs. We characterize level-wise regular block graphs and extended star of blocks achieving this lower bound.

Détail

DOI : 10.7155/jgaa.00420

Keywords: Hamiltonian coloring, Hamiltonian chromatic number, Block graph