Hamiltonian colorings of graphs (Q1763479)

A new chromatic parameter of graphs, the Hamiltonian chromatic number, is introduced in this paper. For vertices \(u\) and \(v\) in a connected graph \(G\) of order \(n\), the length of a longest \(u\)-\(v\) path in \(G\) is denoted by \(D(u,v)\). A Hamiltonian coloring \(c\) of \(G\) is an assignment \(c\) of colors (positive 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\). The value \(\text{hc}(c)\) of a Hamiltonian coloring \(c\) of \(G\) is the maximum color assigned to a vertex of \(G\). The Hamiltonian chromatic number \(\text{hc}(G)\) of \(G\) is \(\min\{\text{hc}(c)\}\) over all Hamiltonian colorings \(c\) of \(G\). This parameter is determined for complete graphs \(K_n\), the complete bipartite graphs \(K_{r,s}\) and for the cycle \(C_n\) as follows: \(\text{hc}(K_n)=1\), \(\text{hc}(K_{1,n-1})=(n-2)^2+1\) for \(n\geq2\), \(\text{hc}(K_{r,r})=r\) for \(r\geq2\), \(\text{hc}(K_{r,1})= (s-1)^2+(r-1)^2\) for \(2\leq r<s\), and \(\text{hc}(C_n)=n-2\). The following two general results are proved as well: (1) For every two integers \(k\) and \(n\) with \(k\geq1\) and \(n\geq3\), there exists a Hamiltonian graph of order \(n\) with Hamiltonian chromatic number \(k\) if and only if \(1\leq k\leq n-2\). (2) If \(G\) is a nontrivial connected graph of order \(n\), then \(\text{hc}(G)\leq(n-2)^2+1\).