Premium
Dirac's map‐color theorem for choosability
Author(s) -
Böhme T.,
Mohar B.,
Stiebitz M.
Publication year - 1999
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/(sici)1097-0118(199912)32:4<327::aid-jgt2>3.0.co;2-b
Subject(s) - combinatorics , mathematics , graph minor , graph , euler's formula , discrete mathematics , graph power , line graph , mathematical analysis
It is proved that the choice number of every graph G embedded on a surface of Euler genus ε ≥ 1 and ε ≠ 3 is at most the Heawood number $H(\epsilon)= \lfloor(7+\sqrt{24\epsilon+1})/2\rfloor$ and that the equality holds if and only if G contains the complete graph K H (ε) as a subgraph. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 327–339, 1999