Minimum span of no-hole (r+1)-distant colorings

Abstract

Given a nonnegative integer r, a no-hole (r + 1)-distant coloring, called N-r-coloring, of a graph G is a function that assigns a nonnegative integer (color) to each vertex such that the separation of the colors of any pair of adjacent vertices is greater than r, and the set of the colors used must be consecutive. Given r and G, the minimum N-r-span of G, nsp(r)(G), is the minimum difference of the largest and the smallest colors used in an N-r-coloring of G if there exists one; otherwise, define nsp,(G) = infinity. The values of nsp(1)(G) (r = 1) for bipartite graphs are given by Roberts [Math. Comput. Modelling, 17 (1993), pp. 139-144]. Given r greater than or equal to 2, we determine the values of nsp(r)(G) for all bipartite graph with at least r - 2 isolated vertices. This leads to complete solutions of nsp(2)(G) for bipartite graphs.