Labeling planar graphs with a condition at distance two
Peter Bella, Daniel Král', Bojan Mohar, Katarína Quittnerová
Abstract
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