Informace o publikaci
Labeling planar graphs with a condition at distance two
| Autoři | |
|---|---|
| Rok publikování | 2007 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | European Journal of Combinatorics |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.ejc.2007.04.019 |
| Popis | 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 lambda(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 lambda(2, 1)(G) <= 32 for every graph G with maximum degree Delta >= 2. We prove the conjecture for planar graphs with maximum degree Delta not equal 3. All our results also generalize to the list-coloring setting. (C) 2007 Elsevier Ltd. All rights reserved. |