Labeling planar graphs with a condition at distance two - Peter Bella; Daniel Král; Bojan Mohar; Katarina Quittnerová (Discrete Mathematics & Theoretical Computer Science, 2005)
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$.