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(1)(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(1)(G) = infinity. Here we investigate the exact values of csp(1)(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) = infinity, 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.