Coloring squares of planar graphs with girth six

DVORAK, Z; Daniel KRÁĽ; P NEJEDLY a R SKREKOVSKI. Coloring squares of planar graphs with girth six. European Journal of Combinatorics. LONDON: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2008, roč. 29, č. 4, s. 838-849. ISSN 0195-6698. Dostupné z: https://dx.doi.org/10.1016/j.ejc.2007.11.005.

Základní údaje

Originální název

Coloring squares of planar graphs with girth six

Autoři

DVORAK, Z; Daniel KRÁĽ; P NEJEDLY a R SKREKOVSKI

Vydání

European Journal of Combinatorics, LONDON, ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2008, 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.678

DOI

http://dx.doi.org/10.1016/j.ejc.2007.11.005

UT WoS

000255363800004

---

Anotace

V originále

Wang and Lih conjectured that for every g >= 5, there exists a number M(g) such that the square of a planar graph G of girth at least g and maximum degree Delta >= M(g) is (Delta + 1)-colorable. The conjecture is known to be true for g >= 7 but false for g is an element of {5, 6}. We show that the conjecture for g = 6 is off by just one, i.e., the square of a planar graph G of girth at least. six and sufficiently large maximum degree is (Delta + 2)-colorable. (c) 2007 Elsevier Ltd. All rights reserved.