### 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