On 3-colorable plane graphs without 5- and 7-cycles
On 3-colorable plane graphs without 5- and 7-cycles
复制标题
DOI：
10.1016/j.jctb.2006.02.005
复制
发表时间：
2006-11
期刊：
影响因子：
--
通讯作者：
Baogang Xu
中科院分区：
文献类型：
--
作者：
Baogang Xu
本文证明了不含5-圈和7-圈且不含相邻三角形的平面图是3-可着色的。这改进了[O. V. Borodin，A.N. Glebov，A. Raspaud，M.R. Salavatipour，Planar graphs without cycles of length from 4 to 7 are 3-colorable，J. Combin. Theory Ser. B 93（2005）303-311]，并为Borodin和Raspaud [O. V. Borodin，A. Raspaud，平面图是3-可着色的一个充分条件，J. Combin。理论系列B 88（2003）17-27]。
In this note, it is proved that every plane graph without 5- and 7-cycles and without adjacent triangles is 3-colorable. This improves the result of [O.V. Borodin, A.N. Glebov, A. Raspaud, M.R. Salavatipour, Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. Combin. Theory Ser. B 93 (2005) 303–311], and offers a partial solution for a conjecture of Borodin and Raspaud [O.V. Borodin, A. Raspaud, A sufficient condition for planar graphs to be 3-colorable, J. Combin. Theory Ser. B 88 (2003) 17–27].