The last excluded case of Dirac's map‐color theorem for choosability
Daniel Král͏̌, Riste Škrekovski · Journal of Graph Theory · 2005
Abstract 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 KHε 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 KH(ε) 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