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
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
Journal title :
Journal of Combinatorial Theory Series B