L(2,1)-Labeling (1992)

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(d1, . . . , dk)-labeling is a nonnegative integer vertex coloring such that the labels on vertices at distance i differ by at least di. We assume that d1 >= . . . >= dk. The maximum label used in such a labeling is called the span of the labeling (the minimum label will be 0), and the aim is to minimize the span of the labeling. For the case of L(2,1)-labeling, the notation \lambda(G) has been used for the minimum span.

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 k2.

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 k2+2k. Chang and Kuo [CK] improved this upper bound to k2+k. Chang et al [CKKLY] generalized this to obtain k2+(d-1)k as an upper bound on the minimum span of an L(d,1)-labeling.

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 Qn and related graphs. SIAM J. Disc. Math. 8 (1995), 499--506.

Index Page; Glossary
Posted 7/03/03