摘要
It is known that every triangle-free plane graph is 3-colorable.However,such a triangle-free plane graph may not be 3-choosable.In this paper,we prove that a triangle-free plane graph is 3-choosable if no 4-cycle in it is adjacent to a 4-or a 5-cycle.This improves some known results in this direction.
It is known that every triangle-free plane graph is 3-colorable.However,such a triangle-free plane graph may not be 3-choosable.In this paper,we prove that a triangle-free plane graph is 3-choosable if no 4-cycle in it is adjacent to a 4-or a 5-cycle.This improves some known results in this direction.
基金
supported by the Zhejiang Provincial Natural Science Foundation ofChina (Grant No. Y6090699)
National Natural Science Foundation of China (Grant No. 10971198)
ZhejiangInnovation Project (Grant No. T200905)
关键词
平面图形
三角形
周期
plane graph,triangle,cycle,coloring,choosability
