A new sufficient condition for a toroidal graph to be 4-choosable

作者：Lv, Jing; Huang, Danjun^*

来源：Discrete Mathematics, 2018, 341(10): 2878-2882.

DOI：10.1016/j.disc.2018.06.041

• Toroidal graph
• Choosability
• Cycle

A graph G is k-choosable if G can be properly colored whenever every vertex has a list of at least k available colors. In this paper, we will proof that if every 5-cycle of toroidal graph G is not adjacent simultaneously to 3-cycles and 4-cycles, then G is 4-choosable. This improves a result shown in Xu and Wu (2017), which stated that if every 5-cycle of planar graph G is not adjacent simultaneously to 3-cycles and 4-cycles, then G is 4-choosable.

• 出版日期2018-10
• 单位浙江师范大学