No-Hole \(2\)-Distant Colorings for Unit Interval Graphs

Abstract

Given a graph, a no-hole \(2\)-distant coloring (also called \(N\)-coloring) is a function \(f\) that assigns to each vertex a non-negative integer (color) such that the separation of the colors of any pair of adjacent vertices must be at least \(2\), and all the colors used by \(f\) form a consecutive set (the no-hole assumption). The minimum consecutive \(N\)-span of \(G\), \(csp(G)\), is the minimum difference of the largest and the smallest colors used in an \(N\)-coloring of \(G\), if there exists such a coloring; otherwise, define \(csp(G) = \infty\). Here we investigate the exact values of \(csp(G)\) for unit interval graphs (also known as \(1\)-unit sphere graphs). Earlier results by Roberts [18] indicate that if \(G\) is a unit interval graph on \(n\) vertices, then \(csp_1(G)\) is either \(2\chi(G) – 1\) or \(2\chi(G) – 2\), if \(n > 2\chi(G) – 1\); \(csp_1(G) = \infty\), if \(n < 2\chi(G) – 1\), where \(\chi(G)\) denotes the chromatic number. We show that in the former case (when \(n > 2\chi(G) – 1\)), both values of \(csp_1(G)\) are attained, and give several families of unit interval graphs such that \(csp_1(G) = 2\chi(G) – 2\). In addition, the exact values of \(csp_1(G)\) are completely determined for unit interval graphs with \(\chi(G) = 3\).