**Originator(s):**
Jerrold R. Griggs and Roger K. Yeh

**Definitions:**
An *L(2,1)-labeling* of a graph is a coloring of the vertices with
nonnegative integers such that the labels on adjacent vertices differ by at
least 2 and the labels on vertices at distance 2 differ by at least 1.
More generally, an *L(d _{1}, . . . , d_{k})-labeling* is
a nonnegative integer vertex coloring such that the labels on vertices
at distance

**Conjecture:**
(Griggs-Yeh [GY]) If *G* is a graph with maximum degree *k*,
then *G* has an *L(2,1)*-labeling with span at most
*k*^{2}.

**Background:**
This concept generalizes the notion of strong coloring, because strong
coloring is the same as *L(1,1)*-labeling. In this language, the
most-studied case is *L(2,1)*-labeling.

**Partial/related results:**
Griggs and Yeh [GY] showed that every graph with maximum degree *k*
has an *L(2,1)*-labeling with span at most *k ^{2}+2k*.
Chang and Kuo [CK] improved this upper bound to

Griggs and Yeh [GY] proved the conjecture for 2-regular graphs.
Füredi and Kang [FK] proved it for 3-regular Hamiltonian
graphs and for the incidence graphs of projective planes.
Griggs and Yeh [GY] showed that the minimum span for *L(2d,d)*-labeling
of *G* can be obtained from the minimum span for *L(2,1)*-labeling
of *G*.

Tight bounds on the maximum span have been obtained for special classes of
graphs like paths, cycles, wheels, complete *k*-partite graphs and graphs
with diameter 2 [GY], trees [CK, GY], etc. Bounds have also been obtained for
various other graph families like chordal graphs and unit interval graphs [S],
hypercubes [GY, J, WGM], and planar graphs [J].

**References:**

[CK] G.J. Chang; D. Kuo,
The *L(2,1)*-labeling problem on graphs.
SIAM J. Discrete Math. 9 (1996), 309--316.

[CKKLY] G.J. Chang; W.-T. Ke; D. Kuo; D. D.-F. Liu; R.K. Yeh,
On *L(d,1)*-labelings of graphs. Discrete Math. 220 (2000), 57--66.

[FK] Z. Füredi; J.-H. Kang,
*L(2,1)*-labeling of 3-regular Hamiltonian graphs, to appear.

[GY] J.R. Griggs; R.K. Yeh,
Labelling graphs with a condition at distance 2.
SIAM J. Discrete Math. 5 (1992), 586--595.

[J] K. Jonas,
Graph coloring analogues with a condition at distance two: L(2,1)-labelling and
list *\lambda*-labellings, Ph.D. thesis, University of South Carolina
(1993).

[S] D. Sakai,
Labelling chordal graphs: distance two condition.
SIAM J. Disc. Math. 7 (1994), 133--140.

[WGM] M.A. Whittlesey; J.P. Georges; D.W. Mauro},
On the *\lambda*-number of *Q _{n}* and related graphs.
SIAM J. Disc. Math. 8 (1995), 499--506.

Posted 7/03/03