Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654852 | European Journal of Combinatorics | 2007 | 39 Pages |
Abstract
An L(2,1)L(2,1)-labeling of a graph is a mapping c:V(G)→{0,…,K}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 KK for which an L(2,1)L(2,1)-labeling of a graph GG exists is denoted by λ2,1(G)λ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λ2,1(G)≤Δ2 for every graph GG with maximum degree Δ≥2Δ≥2. We prove the conjecture for planar graphs with maximum degree Δ≠3Δ≠3. All our results also generalize to the list-coloring setting.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Peter Bella, Daniel Král’, Bojan Mohar, Katarína Quittnerová,