DIMACS TR: 2000-08

Full Color Theorems for L(2,1)-Colorings

Authors: Peter C. Fishburn and Fred S. Roberts


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