Dirac's map-color theorem for choosability

Abstract

It is proved that the choice number of every graph G embedded on a surface of Euler genus e ≥ 1 and e ≠ 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 KH(e) as a subgraph. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 327–339, 1999