zbMATH — the first resource for mathematics

On 3-colorable plane graphs without 5- and 7-cycles. (English) Zbl 1108.05046
Summary: 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 and M. R. Salavatipour [J. Comb. Theory, Ser. B 93, 303–311 (2005; Zbl 1056.05052)], and offers a partial solution for a conjecture of O. V. Borodin and A. Raspaud [J. Comb. Theory, Ser. B 88, 17–27 (2003; Zbl 1023.05046)].

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
Full Text: DOI
[1] 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
[2] Borodin, O.V.; Raspaud, A., A sufficient condition for planar graphs to be 3-colorable, J. combin. theory ser. B, 88, 17-27, (2003) · Zbl 1023.05046
[3] Steinberg, R., The state of the three color problem, (), 211-248 · Zbl 0791.05044
[4] B. Xu, A 3-color theorem on plane graphs without 5-circuits, Acta Math. Sinica, in press · Zbl 1122.05038
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.