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