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.
DIMACS Home Page