DIMACS TR: 2001-10

No-Hole L(2,1)-Colorings

Authors: Peter C. Fishburn and Fred S. Roberts


An L(2,1)-coloring of a graph G is a coloring of G's vertices with integers in {0,1, ..., k} so that adjacent vertices' colors differ by at least two and colors of distance-two vertices differ. We refer to an L(2,1)-coloring as a coloring. The span \lambda(G) of G is the smallest k for which G has a coloring, a span coloring is a coloring whose greatest color is \lambda (G), and the hole index \rho (G) of G is the minimum number of colors in {0,1, ..., \lambda (G) } not used in a span coloring. We say that G is full-colorable if \rho (G) =0. More generally, a coloring of G is a no-hole coloring if it uses all colors between 0 and its maximum color. Both colorings and no-hole colorings were motivated by channel assignment problems. We define the no-hole span \mu (G) of G as \infty if G has no no-hole coloring; otherwise \mu (G) is the minimum k for which G has a no-hole coloring using colors in {0,1, ..., k}. We prove that G is full-colorable if it has \lambda (G) +1 vertices. In addition, if G is not full-colorable and if it has at least \lambda (G) +2 vertices, then \mu (G) \le \lambda (G) + \rho (G). Moreover, for each m >= 1 there is a graph with \rho (G) = m and \mu (G) = \lambda (G) + \rho (G).

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-10.ps.gz
DIMACS Home Page