Labeling planar graphs with a condition at distance two

Abstract

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$.

Keywords

• $l(2 1)$-labeling
• channel assignment problem
• graph coloring
• planar graphs
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]