Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 

 

A generalization of the $ 5$-color theorem


Author: Paul C. Kainen
Journal: Proc. Amer. Math. Soc. 45 (1974), 450-453
MSC: Primary 05C15
DOI: https://doi.org/10.1090/S0002-9939-1974-0345861-4
MathSciNet review: 0345861
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a short topological proof of the $ 5$-color theorem using only the nonplanarity of $ {K_6}$. As a bonus, we find that any graph which becomes planar upon the removal of 2 edges can be $ 5$-colored and that any graph which becomes planar when 5 edges are removed is $ 6$-colorable.


References [Enhancements On Off] (What's this?)

  • [1] Philip Franklin, The four color problem, Scripta Math. 6 (1939), 149–156, 197–210. MR 0001901
  • [2] Herbert Grötzsch, Zur Theorie der diskreten Gebilde. V. Beziehungen zwischen Vierkant- und Dreikantnetzen auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 7 (1958), 353–358 (German). MR 0116318
    Herbert Grötzsch, Zur Theorie der diskreten Gebilde. VI. Ein Kantentransformationssatz für gerade Dreikantnetze mit Viereckssystem auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 7 (1958), 447–456 (German). MR 0116319
    Herbert Grötzsch, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 8 (1958/1959), 109–120 (German). MR 0116320
    Herbert Grötzsch, Zur Theorie der diskreten Gebilde. VIII. Transformation modulo 2 und modulo 3 von Netzen, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 8 (1958/1959), 337–344 (German). MR 0116321
    Herbert Grötzsch, Zur Theorie der diskreten Gebilde. IX. Über Heawoodsche Gleichungen und Möglichstgleichverteilung von Signaturen, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 8 (1958/1959), 747–754 (German). MR 0116322
  • [3] P. J. Heawood, Map colour theorem, Quart. J. Math. 24 (1890), 332-338.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C15

Retrieve articles in all journals with MSC: 05C15


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1974-0345861-4
Keywords: Graph, chromatic number, $ 5$-color theorem, skewness
Article copyright: © Copyright 1974 American Mathematical Society