Minimizing the Number of Holes in \(2\)-Distant Colorings

A 2-distant coloring of a graph is an assignment of positive integers to its vertices so that adjacent vertices cannot get either the same number or consecutive numbers. Given a 2-distant coloring of a graph \(G\), a hole of \(f\) is a finite maximal set of consecutive integers not used by \(f\), and \(h(f)\) is the number of holes of \(f\). In this paper we study the problem of minimizing the number of holes, i.e., we are interested in the number \(h(G) = \min_f h(f)\) where the minimum runs over all 2-distant colorings \(f\) of \(G\). Besides finding exact values for \(h(G)\) for particular graphs, we also relate \(h(G)\) to the path-covering number and the Hamiltonian completion number of \(G\).