Labeling planar graphs with a condition at distance two

BELLA, P; Daniel KRÁĽ; B MOHAR a K QUITTNEROVA. Labeling planar graphs with a condition at distance two. European Journal of Combinatorics. LONDON: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2007, roč. 28, č. 8, s. 2201-2239. ISSN 0195-6698. Dostupné z: https://doi.org/10.1016/j.ejc.2007.04.019.

Základní údaje

Originální název

Labeling planar graphs with a condition at distance two

Autoři

BELLA, P; Daniel KRÁĽ; B MOHAR a K QUITTNEROVA

Vydání

European Journal of Combinatorics, LONDON, ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2007, 0195-6698

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.651

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1016/j.ejc.2007.04.019

UT WoS

000250712900013

---

Anotace

V originále

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.