科研之友
微信
新浪微博
Facebook
分享链接
摘要
Given an edge coloring F of a graph G, a vertex coloring of G is adapted to F if no color appears at the same time on an edge and on its two endpoints. If for some integer k, a graph G is such that given any list assignment L to the vertices of G, with vertical bar L(v)vertical bar >= k for all v, and any edge coloring F of G, G admits a coloring c adapted to F where c(v) is an element of L(v) for all v, then G is said to be adaptably k-choosable. In this note, we prove that K(5)-minor-free graphs are adaptably 4-choosable, which implies that planar graphs are adaptably 4-colorable and answers a question of Hell and Zhu. We also prove that triangle-free planar graphs are adaptably 3-choosable and give negative results on planar graphs without 4-cycle, planar graphs without 5-cycle, and planar graphs without triangles at distance t, for any t >= 0.
- 出版日期2009-10
- 单位中山大学
