On Hamiltonian colorings of graphs (Q1772412)

The authors give a lower bound for the circumference of a graph in terms of the number of vertices that receive colors between two specified colors in a Hamiltonian coloring of the graph. As a consequence, if there exists a Hamiltonian coloring of a connected graph \(G\) of order \(n\) such that at least \((n+2)/2\) vertices of \(G\) are colored with one of two consecutive colors, then the circumference of \(G\) is at least \(n-1\).