Title of article
Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
Author/Authors
Borodin، نويسنده , , O.V. and Glebov، نويسنده , , A.N. and Montassier، نويسنده , , M. and Raspaud، نويسنده , , A.، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2009
Pages
6
From page
668
To page
673
Abstract
It is known that planar graphs without cycles of length from 4 to 7 are 3-colorable [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]. We improve this result by proving that every planar graph without 5- and 7-cycles and without adjacent triangles is 3-colorable. Also, we give counterexamples to the proof of the same result in [B. Xu, On 3-colorable plane graphs without 5- and 7-cycles, J. Combin. Theory Ser. B 96 (2006) 958–963].
Keywords
Steinbergיs conjecture , Coloring , Three Color Problem , Planar graphs
Journal title
Journal of Combinatorial Theory Series B
Serial Year
2009
Journal title
Journal of Combinatorial Theory Series B
Record number
1528861
Link To Document