×

zbMATH — the first resource for mathematics

Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable. (English) Zbl 1184.05024
0. V. Borodin, A. N. Glebvov, A. Raspaud and M. R. Salavatipour [J. Comb. Theory, Ser. B 93, No. 2, 303–311 (2005; Zbl 1056.05052)] showed that planar graphs without cycles of length 4, 5, 6, or 7 are 3-colorable. The present authors improve this result by proving that planar graphs without cycles of length 5 or 7 and also without adjacent triangles are 3-colorable. They also give counterexamples to the argument given for the same result by B. Xu [J. Comb. Theory, Ser. B 96, No. 6, 958–963 (2006; Zbl 1108.05046)].

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abbott, H.L.; Zhou, B., On small faces in 4-critical graphs, Ars combin., 32, 203-207, (1991) · Zbl 0755.05062
[2] Aksenov, V.A.; Borodin, O.V.; Glebov, A.N., On extending 3-colorability from a 6-face to a planar triangle-free graph, Diskretn. anal. issled. oper., 10, 3, 3-11, (2003), (in Russian) · Zbl 1047.05014
[3] Aksenov, V.A.; Borodin, O.V.; Glebov, A.N., Extending 3-colorability from a 7-face to a planar triangle-free graph, Sib. elektron. mat. izv., 1, 117-128, (2004), (in Russian) · Zbl 1077.05039
[4] Borodin, O.V., To the paper of H.L. abbott and B. zhou on 4-critical planar graphs, Ars combin., 43, 191-192, (1996) · Zbl 0881.05037
[5] Borodin, O.V., Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. graph theory, 21, 2, 183-186, (1996) · Zbl 0838.05039
[6] Borodin, O.V.; Glebov, A.N.; Raspaud, A.; Salavatipour, M.R., Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. combin. theory ser. B, 93, 303-311, (2005) · Zbl 1056.05052
[7] Borodin, O.V.; Glebov, A.N.; Jensen, T.R.; Raspaud, A., Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable, Sib. elektron. mat. izv., 3, 428-440, (2006) · Zbl 1119.05037
[8] Gimbel, J.; Thomassen, C., Coloring graphs with fixed genus and girth, Trans. amer. math. soc., 349, 4555-4564, (1997) · Zbl 0884.05039
[9] Sanders, D.P.; Zhao, Y., A note on the three color problem, Graphs combin., 11, 91-94, (1995) · Zbl 0824.05023
[10] Steinberg, R., The state of the three color problem, (), 211-248 · Zbl 0791.05044
[11] Xu, B., On 3-colorable plane graphs without 5- and 7-cycles, J. combin. theory ser. B, 96, 958-963, (2006) · Zbl 1108.05046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.