The state of the three color problem. (English) Zbl 0791.05044

Gimbel, John (ed.) et al., Quo vadis, graph theory? A source book for challenges and directions. Amsterdam: North-Holland. Ann. Discrete Math. 55, 211-248 (1993).
This interesting survey paper describes the origin of the three color problem and virtually all the major results and conjectures existing in the literature. Its chapters are the following: 1. Introduction. 2. The origin of the three color problem (Heawood’s second paper, the three color theorem). 3. Basic results (three interrelated results, outerplanar and cubic graphs, Brook’s theorem (cubic case)). 4. Triangle-free graphs and chromatic number. 5. Grötzsch’s theorem (variations on Grötzsch’s approach). 6. Grünbaum’s theorem and Aksionov’s theorem. 7. The distance of the triangles. 8. Uniquely 3-colorable planar graphs. 9. Restricting 4-cycles and 5-cycles. 10. Algorithms and complexity (the Petford-Welsh algorithm). 11. Geometric problems (plane 4-regular graphs with cycle-decompositions, the circle-triangle conjecture). 12. Relationship to four coloring (triangle-colored graphs, Toft’s color reduction). 13. Counting 3-colorings. 14. Applications of 3-coloring (Chvátal’s art gallery theorem, computing with 3-colorable graphs). 15. Nowhere-zero 3-flows. 16. Conclusions. The bibliography includes 128 references and an appendix contains an outline of a proof of Grünbaum’s theorem.
For the entire collection see [Zbl 0773.00007].


05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
05C80 Random graphs (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science