Dirac's map-color theorem for choosability

Citation
T. Bohme et al., Dirac's map-color theorem for choosability, J GRAPH TH, 32(4), 1999, pp. 327-339
Citations number
18
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF GRAPH THEORY
ISSN journal
03649024 → ACNP
Volume
32
Issue
4
Year of publication
1999
Pages
327 - 339
Database
ISI
SICI code
0364-9024(199912)32:4<327:DMTFC>2.0.ZU;2-4
Abstract
It is proved that the choice number of every graph G embedded on a surface of Euler genus epsilon greater than or equal to 1 and epsilon not equal 3 i s at most the Heawood number H(epsilon) = [(7 + root 24 epsilon + 1)/2] and that the equality holds if and only if G contains the complete graph K-H(e psilon) as a subgraph. (C) 1999 John Wiley Br Sons, Inc. J Graph Theory 32: 327-339, 1999.