The last excluded case of Dirac's map-color theorem for choosability

✍ Scribed by Daniel Král'; Riste S̆krekovski

• Publisher: John Wiley and Sons
• Year: 2006
• Tongue: English
• Weight: 294 KB
• Volume: 51
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20136

✦ Synopsis

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