The last excluded case of Dirac's Map-Color Theorem for choosability

KRÁĽ, Daniel a R SKREKOVSKI. The last excluded case of Dirac's Map-Color Theorem for choosability. Journal of Graph Theory. HOBOKEN: Wiley, 2006, roč. 51, č. 4, s. 319-354. ISSN 0364-9024. Dostupné z: https://dx.doi.org/10.1002/jgt.20136.

Základní údaje

Originální název

The last excluded case of Dirac's Map-Color Theorem for choosability

Autoři

KRÁĽ, Daniel a R SKREKOVSKI

Vydání

Journal of Graph Theory, HOBOKEN, Wiley, 2006, 0364-9024

---

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.403

DOI

http://dx.doi.org/10.1002/jgt.20136

UT WoS

000236079200004

Klíčová slova anglicky

graph coloring; list coloring; Heawood's formula; Dirac's Map-Color Theorem; graphs on surfaces

---

Anotace

V originále

In 1890, Heawood established the upper bound H(epsilon) = [7 + root 24 epsilon+ 1/2] on the chromatic number of every graph embedded on a surface of Euier genus epsilon >= 1. Almost 80 years later, the bound was shown to be tight by Ringel and Youngs. These two results have became known under the name of the Map-Color Theorem. In 1956, Dirac refined this by showing that the upper bound H(epsilon) is obtained only if a graph G contains K-H(epsilon) as a subgraph except for three surfaces. Albertson and Hutchinson settled these excluded cases in 1979. This result is nowadays known as Dirac's Map-Color Theorem. Bohme, Mohar, and Stiebitz extended Dirac's Map-Color Theorem to the case of choosability by showing that G is (H(epsilon) - 1)-choosable unless G contains K-H(epsilon) as a subgraph for epsilon >= 1 and epsilon not equal 3. In the present paper, we settle the excluded case of epsilon = 3. (C) 2005 Wiley Periodicals, Inc.