## DIMACS TR: 2001-10

## No-Hole L(2,1)-Colorings

### Authors: Peter C. Fishburn and Fred S. Roberts

**
ABSTRACT
**

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