zbMATH — the first resource for mathematics

A note on the three color problem. (English) Zbl 0824.05023
In 1990 Paul Erdős asked: Is there an integer \(k\geq 5\) such that if \(G\) is a planar graph without \(i\)-circuits, \(4\leq i\leq k\), then \(G\) is 3- colorable? A year later H. L. Abbott and B. Zhou answered this question affirmatively by proving the above with \(k= 11\). This note strengthens their result by showing that \(G\) is 3-colorable, if it is planar without \(i\)-circuits for \(i\) from 4 through 9.
Reviewer: M.Kubale (Gdańsk)

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
Full Text: DOI
[1] Abbott, H.L., Zhou, B.: On small faces in 4-critical planar graphs. Ars Combin.32, 203–207 (1991) · Zbl 0755.05062
[2] Aksionov, V.A., Melnikov, L.S.: Essay on the theme: The three color problem. Combinatorics, Colloq. Math. Soc. János Bolyai18, 23–34 (1976)
[3] Aksionov, V.A., Melnikov, L.S.: Some counterexamples associated with the three color problem. J. Comb. Theory ser.B28, 1–9 (1980) · Zbl 0434.05033 · doi:10.1016/0095-8956(80)90051-9
[4] Erdös, P.: informal discussion during the conference ”Quo Vadis, Graph Theory?” University of Alaska, Fairbanks, Alaska, August (1990)
[5] Steinberg, R.: The state of the three color problem. Ann. Discrete Math.55, 211–248 (1993) · Zbl 0791.05044 · doi:10.1016/S0167-5060(08)70391-1
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.