Labeling planar graphs with a condition at distance two

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. The smallest K for which an L ( 2 , 1 ) -labeling of a graph G exists is denoted by λ 2 , 1 ( G ) . Griggs and Yeh [J.R. Griggs, R.K. Yeh, Labeling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586–595] conjectured that λ 2 , 1 ( G ) ≤ Δ 2 for every graph G with maximum degree Δ ≥ 2 . We prove the conjecture for planar graphs with maximum degree Δ ≠ 3 . All our results also generalize to the list-coloring setting.