Authors: Peter Bella ¹; Daniel Král ²; Bojan Mohar ³; Katarina Quittnerová ⁴

• 1 Department of Mathematical Analysis
• 2 Department of Applied Mathematics [Prague]
• 3 Department of Mathematics
• 4 Faculty of Mathematics and Physics [Ljubljana]

An $L(2,1)$-labeling of a graph is a mapping $c:V(G) \to \{0,\ldots,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 $\Delta$ has an $L(2,1)$-labeling with $K \leq \Delta^2$. We verify the conjecture for planar graphs with maximum degree $\Delta \neq 3$.