Adaptable choosability of planar graphs with sparse short cycles

作者：Guan, Albert; Zhu, Xuding^*

来源：Discrete Mathematics, 2009, 309(20): 6044-6047.

DOI：10.1016/j.disc.2009.05.004

• Adapted colouring
• List colouring
• Planar graphs

Given a (possibly improper) edge colouring F of a graph G,a vertex colouring of G is adapted to F if no colour appears at the same time on an edge and on its two endpoints. A graph G is called adaptably k-choosable (for some positive integer k) if for any list assignment L to the vertices of G, with |L(v)| >= k for all v, and any edge colouring F of G, G admits a colouring c adapted to F where CO) E L(v) for all v. This paper proves that a planar graph G is adaptably 3-choosable if any two triangles in adjacent to a 4-cycle.

• 出版日期2009-10-28
• 单位中山大学