zbMATH — the first resource for mathematics

A 3-color theorem on plane graphs without 5-circuits. (English) Zbl 1122.05038
Summary: We prove that every plane graph without 5-circuits and without triangles of distance less than 3 is 3-colorable. This improves the main result of O. V. Borodin and A. Raspaud [J. Comb. Theory, Ser. B 88, 17–27 (2003; Zbl 1023.05046)], and provides a new upper bound to their conjecture.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Steinberg, R.: The state of the three color problem, Quo Vadis. Graph Theory? J. Gimbel, J. W. Kennedy & L. V. Quintas (eds). Ann Discrete Math., 55, 211–248 (1993) · Zbl 0791.05044
[2] Borodin, O. V.: Structural properties of plane graphs without adjacent triangles and an application to 3-colorings. Journal of Graph Theory, 21(2), 183–186 (1996) · Zbl 0838.05039
[3] Abbott, H. L., Zhou, B.: On small faces in 4-critical graphs. Ars Combin., 32, 203–207 (1991) · Zbl 0755.05062
[4] Sanders, D. P., Zhao, Y.: A note on the three color problem. Graphs and Combinatorics, 11, 91–94 (1995) · Zbl 0824.05023
[5] Borodin, O. V., et al.: Planar graphs without cycles of length from 4 to 7 are 3-colorable. Journal of Combinatorial Theory, Ser. B, 93, 303–311 (2005) · Zbl 1056.05052
[6] Xu, B.: On 3-colorable plane graphs without 5- and 7-circuits. Journal of Combinatorial Theory, Ser. B, in press · Zbl 1108.05046
[7] Borodin, O. V., Raspaud, A.: A su.cient condition for planar graphs to be 3-colorable. Journal of Combinatorial Theory, Ser. B, 88, 17–27 (2003) · Zbl 1023.05046
[8] Xu, B.: On 3-colorings of plane graphs. Acta Math. Appl. Sinica, 20, 597–604 (2004) · Zbl 1062.05063
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.