zbMATH — the first resource for mathematics

A sufficient condition for planar graphs to be 3-colorable. (English) Zbl 1023.05046
The authors prove that every proper 3-coloring of a face of size 3 or 7 in a connected planar graph without pairs of 3-cycles at distance less than 4 and without 5-cycles can be extended to a proper 3-coloring of the whole graph. Form this and Grötzsch’s theorem, it follows that planar graphs without 3-cycles at distance less than 4 and without 5-cycles are 3-colorable. The authors conjecture that planar graphs without 5-cycles in which every two 3-cycles are vertex-disjoint (or every two 3-cycles are edge-disjoint) are 3-colorable.

05C15 Coloring of graphs and hypergraphs
graph coloring
Full Text: DOI
[1] Garey, M.R.; Johnson, D.S.; Stockmeyer, L.J., Some simplified NP-complete graph problems, Theoret. comput. sci., 1, 237-267, (1976) · Zbl 0338.05120
[2] Grötzsch, H., Ein dreifarbensatz für dreikreisfreie netze auf der kugel, wiss. Z. martin luther univ. halle Wittenberg, Math.-nat. reihe, 8, 109-120, (1959)
[3] Havel, I., On a conjecture of B. grünbaum, J. combin. theory, 7, 184-186, (1969) · Zbl 0177.26805
[4] Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley-Interscience New York · Zbl 0971.05046
[5] R. Steinberg, The state of the three color problem, in: J. Gimbel, J.W. Kennedy, L.V. Quintas (Eds.), Quo Vadis, Graph Theory? Ann. Discrete Math. 55 (1993) 211-248.
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.