Bounds for the Hamiltonian chromatic number of a graph. (English) Zbl 1029.05059

Authors’ abstract: Let \(G\) be a nontrivial connected graph of order \(n\). For \(u,v\in V(G)\), the detour distance \(D(u,v)\) between \(u\) and \(v\) is the length of a longest \(u\)-\(v\) path in \(G\). A Hamiltonian coloring of \(G\) is an assignment \(c\) of colors (positive integers) to the vertices of \(G\) that satisfies \(D(u,v)+|c(u)- c(v)|\geq n-1\) for every two distinct vertices \(u\) and \(v\) of \(G\). The value of a Hamiltonian coloring \(c\) of \(G\) is \(\text{hc}(c)= \max\{c(v): v\in V(G)\}\). The Hamiltonian chromatic number \(\text{hc}(G)\) of \(G\) is the minimum value \(\text{hc}(c)\) among all Hamiltonian colorings \(c\) of \(G\). We provide bounds for the Hamiltonian chromatic number of a graph in terms of its order and detour distances in the graph.


05C15 Coloring of graphs and hypergraphs
05C12 Distance in graphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C45 Eulerian and Hamiltonian graphs