×

An unavoidable set of \(D\)-reducible configurations. (English) Zbl 1221.05165

Summary: 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).

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 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. · Zbl 0506.05028
[2] K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429 – 490. K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21 (1977), no. 3, 491 – 567. K. Appel and W. Haken, The class check lists corresponding to the supplement: ”Every planar map is four colorable. I. Discharging” (Illinois J. Math. 21 (1977), no. 3, 429 – 490), Illinois J. Math. 21 (1977), no. 3, C1-C210. (microfiche supplement). K. Appel and W. Haken, Supplement to: ”Every planar map is four colorable. I. Discharging” (Illinois J. Math. 21 (1977), no. 3, 429 – 490) by Appel and Haken; ”II. Reducibility” (ibid. 21 (1977), no. 3, 491 – 567) by Appel, Haken and J. Koch, Illinois J. Math. 21 (1977), no. 3, 1 – 251. (microfiche supplement). Kenneth Appel and Wolfgang Haken, The solution of the four-color-map problem, Sci. Amer. 237 (1977), no. 4, 108 – 121, 152. , https://doi.org/10.1038/scientificamerican1077-108 Kenneth Appel and Wolfgang Haken, Every planar map is four colorable, J. Recreational Math. 9 (1976/77), no. 3, 161 – 169. · Zbl 0387.05009
[3] K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429 – 490. K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21 (1977), no. 3, 491 – 567. K. Appel and W. Haken, The class check lists corresponding to the supplement: ”Every planar map is four colorable. I. Discharging” (Illinois J. Math. 21 (1977), no. 3, 429 – 490), Illinois J. Math. 21 (1977), no. 3, C1-C210. (microfiche supplement). K. Appel and W. Haken, Supplement to: ”Every planar map is four colorable. I. Discharging” (Illinois J. Math. 21 (1977), no. 3, 429 – 490) by Appel and Haken; ”II. Reducibility” (ibid. 21 (1977), no. 3, 491 – 567) by Appel, Haken and J. Koch, Illinois J. Math. 21 (1977), no. 3, 1 – 251. (microfiche supplement). Kenneth Appel and Wolfgang Haken, The solution of the four-color-map problem, Sci. Amer. 237 (1977), no. 4, 108 – 121, 152. , https://doi.org/10.1038/scientificamerican1077-108 Kenneth Appel and Wolfgang Haken, Every planar map is four colorable, J. Recreational Math. 9 (1976/77), no. 3, 161 – 169. · Zbl 0387.05009
[4] 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. · Zbl 0681.05027
[5] G.D. Birkhoff, The reducibility of maps, Amer. J. Math. 70 (1913), 114-128.
[6] Arthur Bernhart, Another reducible edge configuration, Amer. J. Math. 70 (1948), 144 – 146. · Zbl 0034.40102 · doi:10.2307/2371940
[7] D.I.A. Cohen, Block-count reducibility and the four-color theorem, manuscript.
[8] 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. · Zbl 0908.05041
[9] 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. · Zbl 0764.05026
[10] G. Gonthier, A computer-checked proof of the four-color theorem, http://research.microsoft. com/\( \sim\)gonthier/fourcolor.pdf. · Zbl 1195.05026
[11] W. Haken, Shimamoto’s construction, manuscript (1971), available at http://www.math. ubc. ca/\( \sim\)jpsteinb/index.html.
[12] Heinrich Heesch, Untersuchungen zum Vierfarbenproblem, B. I. Hochschulskripten, vol. 810/810, Bibliographisches Institut, Mannheim-Vienna-Zürich, 1969 (German). · Zbl 0187.20904
[13] A. B. Kempe, On the Geographical Problem of the Four Colours, Amer. J. Math. 2 (1879), no. 3, 193 – 200. · doi:10.2307/2369235
[14] 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).
[15] Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997), no. 1, 2 – 44. · Zbl 0883.05056 · doi:10.1006/jctb.1997.1750
[16] -, Reducibility in the four colour theorem, available at http://math.gatech. edu/\( \sim\)thomas/OLDFTP/four.
[17] -, Discharging cartwheels, available at http://math.gatech.edu/\( \sim\)thomas/ OLDFTP/four.
[18] W.R. Stromquist, Some aspects of the four color problem, Ph.D., Harvard University, 1975. Available at http:// www.walterstromquist.com. · Zbl 0313.05109
[19] Hassler Whitney and W. T. Tutte, Kempe chains and the four colour problem, Studies in graph theory, Part II, Math. Assoc. Amer., Washington, D.C., 1975, pp. 378 – 413. Studies in Math., Vol. 12. · Zbl 0328.05107
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.