A $k$-L(2,1)-labeling of a graph is a function from its vertex set into the
set $\{0,...,k\}$, such that the labels assigned to adjacent vertices differ by
at least 2, and labels assigned to vertices of distance 2 are different. It is
known that finding the smallest $k$ admitting the existence of a
$k$-L(2,1)-labeling of any given graph is NP-Complete.