Premium
The last excluded case of Dirac's map‐color theorem for choosability
Author(s) -
Král' Daniel,
S̆krekovski Riste
Publication year - 2006
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20136
Subject(s) - mathematics , combinatorics , dirac (video compression format) , upper and lower bounds , graph , list coloring , discrete mathematics , graph power , mathematical analysis , quantum mechanics , physics , neutrino , line graph
In 1890, Heawood established the upper bound $H ( \varepsilon )= \left \lfloor 7+\sqrt {24\varepsilon +1}/{2}\right \rfloor$ on the chromatic number of every graph embedded on a surface of Euler genus ε ≥ 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 (ε) is obtained only if a graph G contains K H ε 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. Böhme, Mohar, and Stiebitz extended Dirac's Map‐Color Theorem to the case of choosability by showing that G is ( H (ε) − 1)‐choosable unless G contains K H (ε) as a subgraph for ε ≥ 1 and ε ≠ 3. In the present paper, we settle the excluded case of ε = 3. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 319–354, 2006