DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Labeling planar graphs with a condition at distance two

Peter Bella, Daniel Král', Bojan Mohar, Katarína Quittnerová


An L(2,1)-labeling of a graph is a mapping c:V(G)→{0,…,K} such that the labels assigned to neighboring vertices differ by at least 2 and the labels of vertices at distance two are different. Griggs and Yeh [SIAM J. Discrete Math. 5 (1992), 586--595] conjectured that every graph G with maximum degree Δ has an L(2,1)-labeling with K≤Δ2. We verify the conjecture for planar graphs with maximum degree Δ≠3.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional