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

Chartrand, Gary; Nebeský, Ladislav; Zhang, Ping

Congr. Numerantium 157, 113-125 (2002).

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.

Reviewer: Saul Stahl (Lawrence)

MSC:

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

Keywords:

detour distance; Hamiltonian coloring