Hamiltonian chromatic number of trees

Abstract

Let $G$ be a simple finite connected graph of order $n$. The detour distance between two distinct vertices $u$ and $v$ denoted by $D(u,v)$ is the length of a longest $uv$-path in $G$. A hamiltonian coloring $h$ of a graph $G$ of order $n$ is a mapping $h:V(G)\to \{0,1,2,...\}$ such that $D(u,v)+|h(u)-h(v)|\ge n-1$, for every two distinct vertices $u$ and $v$ of $G$. The span of $h$, denoted by $span(h)$, is $\max \{|h(u)-h(v)|:u,v\in V(G)\}$. The hamiltonian chromatic number of $G$ is defined as $hc(G):=\min \{span(h)\}$ with minimum taken over all hamiltonian coloring $h$ of $G$. In this paper, we give an improved lower bound for the hamiltonian chromatic number of trees and give a necessary and sufficient condition to achieve the improved lower bound. Using this result, we determine the hamiltonian chromatic number of two families of trees.

This is a final version appeared in proceedings of RAGT 2019 Conference