An unavoidable set of 𝐷-reducible configurations

Steinberger, John

doi:10.1090/S0002-9947-2010-05092-5

An unavoidable set of $D$-reducible configurations
HTML articles powered by AMS MathViewer

by John P. Steinberger PDF

Trans. Amer. Math. Soc. 362 (2010), 6633-6661 Request permission

Abstract:

We give a new proof of the four-color theorem by exhibiting an unavoidable set of 2822 $D$-reducible configurations. The existence of such a set had been conjectured by several researchers including Stromquist (1975), Appel and Haken (1977), and Robertson, Sanders, Seymour and Thomas (1997).

References

Frank Allaire, Another proof of the four colour theorem. I, Proceedings of the Seventh Manitoba Conference on Numerical Mathematics and Computing (Univ. Manitoba, Winnipeg, Man., 1977) Congress. Numer., XX, Utilitas Math., Winnipeg, Man., 1978, pp. 3–72. MR 535003
K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR 543792
K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21 (1977), no. 3, 491–567. MR 543793
Kenneth Appel and Wolfgang Haken, Every planar map is four colorable, Contemporary Mathematics, vol. 98, American Mathematical Society, Providence, RI, 1989. With the collaboration of J. Koch. MR 1025335, DOI 10.1090/conm/098
G.D. Birkhoff, The reducibility of maps, Amer. J. Math. 70 (1913), 114–128.
Arthur Bernhart, Another reducible edge configuration, Amer. J. Math. 70 (1948), 144–146. MR 23513, DOI 10.2307/2371940
D.I.A. Cohen, Block-count reducibility and the four-color theorem, manuscript.
Rudolf Fritsch and Gerda Fritsch, The four-color theorem, Springer-Verlag, New York, 1998. History, topological foundations, and idea of proof; Translated from the 1994 German original by Julie Peschke. MR 1633950, DOI 10.1007/978-1-4612-1720-6
S. J. Gismondi and E. R. Swart, A new type of $4$-colour reducibility, Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), 1991, pp. 33–48. MR 1152056
G. Gonthier, A computer-checked proof of the four-color theorem, http://research.microsoft.com/$\sim$gonthier/fourcolor.pdf.
W. Haken, Shimamoto’s construction, manuscript (1971), available at http://www.math.ubc.ca/$\sim$jpsteinb/index.html.
Heinrich Heesch, Untersuchungen zum Vierfarbenproblem, B. I. Hochschulskripten, vol. 810/810, Bibliographisches Institut, Mannheim-Vienna-Zürich, 1969 (German). MR 0248048
A. B. Kempe, On the Geographical Problem of the Four Colours, Amer. J. Math. 2 (1879), no. 3, 193–200. MR 1505218, DOI 10.2307/2369235
Jean Mayer, Une propriété des graphes minimaux dans le problème des quatre couleurs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 291–295 (French, with English summary). MR 539995
Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997), no. 1, 2–44. MR 1441258, DOI 10.1006/jctb.1997.1750
—, Reducibility in the four colour theorem, available at http://math.gatech. edu/$\sim$thomas/OLDFTP/four.
—, Discharging cartwheels, available at http://math.gatech.edu/$\sim$thomas/ OLDFTP/four.
W.R. Stromquist, Some aspects of the four color problem, Ph.D., Harvard University, 1975. Available at http:// www.walterstromquist.com.
Hassler Whitney and W. T. Tutte, Kempe chains and the four colour problem, Studies in graph theory, Part II, Studies in Math., Vol. 12, Math. Assoc. Amer., Washington, D.C., 1975, pp. 378–413. MR 0392651