## 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