Publication details
The last excluded case of Dirac's Map-Color Theorem for choosability
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Periodical |
| Magazine / Source | Journal of Graph Theory |
| Citation | |
| Doi | http://dx.doi.org/10.1002/jgt.20136 |
| Keywords | graph coloring; list coloring; Heawood's formula; Dirac's Map-Color Theorem; graphs on surfaces |
| Description | 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. |