Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657092 | Journal of Combinatorial Theory, Series B | 2009 | 6 Pages |
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].
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics