期刊
SIAM JOURNAL ON DISCRETE MATHEMATICS
卷 24, 期 4, 页码 1632-1637出版社
SIAM PUBLICATIONS
DOI: 10.1137/100796649
关键词
graph coloring; graph minor; choosability; list coloring; Hadwiger Conjecture
资金
- Knut and Alice Wallenberg Foundation
- Australian Research Council
Thomassen (J. Combin. Theory Ser. B, 62 (1994), pp. 180-181) proved that every planar graph is 5-choosable. This result was generalized by. Skrekovski (Discrete Math., 190 (1998), pp. 223- 226) and He, Miao, and Shen (Discrete Math., 308 (2008), pp. 4024-4026), who proved that every K-5-minor-free graph is 5-choosable. Both proofs rely on the characterization of K-5-minor-free graphs due to Wagner (Math. Ann., 114 (1937), pp. 570-590). This paper proves the same result without using Wagner's structure theorem or even planar embeddings. Given that there is no structure theorem for graphs with no K-6-minor, we argue that this proof suggests a possible approach for attacking the Hadwiger Conjecture.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据