Dirac's map-color theorem for choosability
Dirac's map-color theorem for choosability
复制标题
DOI：
10.1002/(sici)1097-0118(199912)32:4
复制
发表时间：
1999-12
期刊：
影响因子：
--
通讯作者：
T. Böhme;B. Mohar;M. Stiebitz
中科院分区：
文献类型：
--
作者：
T. Böhme;B. Mohar;M. Stiebitz
证明了嵌入在欧拉属e≥1且e≠3的曲面上的每个图G的选择数至多为Heawood数$H(\epsilon)= \lfloor(7+\sqrt{24\epsilon+1})/2\rfloor$，且当且仅当G包含完全图KH(e)为子图时成立。©1999 John Wiley ＆ Sons, Inc[J] .图论学报（自然科学版），2009
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