DIMACS TR: 2000-08
Full Color Theorems for L(2,1)-Colorings
Authors: Peter C. Fishburn and Fred S. Roberts
ABSTRACT
The span $\la (G)$ of a graph $G$ is the smallest $k$ for which $G$'s
vertices can be $L(2,1)$-colored, i.e., colored with integers in
$\{0,1, \ldots, k \}$ so that adjacent vertices' colors differ by at
least two, and colors of vertices at distance two differ. $G$ is
full-colorable if some such coloring uses all colors in $\{0,1,
\ldots, \la (G) \}$ and no others. We prove that all trees except
stars are full-colorable. The connected graph $G$ with the smallest
number of vertices exceeding $\la (G)$ that is not full-colorable is
$C_6$. We describe an array of other connected graphs that are not
full-colorable and go into detail on full-colorability of graphs of
maximum degree four or less.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-08.ps.gz
DIMACS Home Page