[hal-01184374] Labeling planar graphs with a condition at distance two

An L(2,1)-labeling of a graph is a mapping c:V(G)→\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 Δ has an L(2,1)-labeling with K≤Δ ^2. We verify the conjecture for planar graphs with maximum degree Δ ≠3.

from HAL : Dernières publications http://ift.tt/1DQQNBy