Feature Column

Colorful Mathematics: I


6. References

Appel, K. and W. Haken, Every Planar Map is Four Colorable, American Mathematical Society, Providence, 1989.

Borodin, O., On cyclic coloring of planar graphs, Discrete Math., 100 (1992) 281-289.

Borodin, O., Cyclic degree and cyclic colorings of 3-polytopes, J. of Graph Theory, 23 (1996) 225-231.

Borodin, O., Structural theorem on plane graphs with application to the entire coloring number, J. of Graph Theory, 23 (1996) 233-239.

Diestel, R., Graph Theory, Springer-Verlag, New York, 1997.

Dirac, G., Percy John Heawood, J. London Math. Soc., 38 (1963) 263-277.

Fiorini, S. and R. Wilson, Edge-colourings of Graphs, Research Notes in Mathematics, Vol. 16, Pitman, 1977.

Fritsch, R. and G. Fritsch, The Four-Color Theorem, Springer-Verlag, New York, 1998.

Grünbaum, B., Convex Polytopes, Wiley-Interscience, New York, 1967. (Second edition, 2003.)

Gutner, S., The complexity of planar graph choosability, Discrete Math., 159 (1996) 119-130.

Hadwiger, H., Über eine Klassifikation der Streckenkomplexe, Vierteljahrschriften der Naturforschungsgellschaft Zürich, 88 (1943) 133-142.

Jensen, T. and B. Toft, Graph Coloring Problems, Wiley, New York, 1995.

Kronk, H., and J. Michem, The entire chromatic number of a normal graph is at most seven, Bull. Amer. Math. Soc., 78 (1972) 799-800.

Kronk, H. and J. Mitchem, A seven-color theorem on the sphere, Discrete Math., 5 (1973) 255-260.

Lebesgue, H., Quelques consequences simple de la formule d'Euler, J. de Math. Pures et Appl., 19 (1940) 27-43.

May, K., The origin of the four-colour conjecture, Isis, 56 (1965) 346-348.

Mirzakhani, M., A small non-4-choosable planar graph, Bull. Inst. Combin. Appl., 17 (1996) 15-18.

Mohar, B. and C. Thomassen, Graphs on Surfaces, John Hopkins University Press, Baltimore, 2001.

Ore, O. The Four Color Problem, Academic Press, New York, 1967.

Plummer, M. and B. Toft, Cyclic coloration of 3-polytopes, J. Graph Theory, 11 (1987) 507-515.

Ringel, G. Map Color Theorem, Springer-Verlag, New York, 1974.

Robertson, N., and D. Sanders, P. Seymour, R. Thomas, The four color theorem, J. Combinatorial Theory Ser. B. 70 (1997) 2-44.

Robertson, N., and D. Sanders, P. Seymour, R. Thomas, Every 2-connected cubic graph with no Petersen minor is 3-edge colorable. (To appear.)

Robertson, N. and P. Seymour, Graph minors - a survey. Surveys in Combinatorics, 1985, London Math. Soc. Lecture Note Series, Volume 103, Cambridge U. Press, Cambridge, p. 153-171.

Robertson, N. and P. Seymour, R. Thomas, Hadwiger's conjecture for K6-free graphs, Combinatorica, 13 (1993) 279-361.

Saaty, T. and P. Kainen, The Four-Color Problem: Assaults and Conquest, McGraw Hill, New York, 1977.

Sanders, D. and Y. Zhao, On simultaneous edge-face colorings of plane graphs, Combinatorica, 17 (1997) 441-445.

Sanders, D. and Y. Zhao, On total 9-coloring planar graphs of maximum degree seven, J. Graph Theory, 31 (1999) 63-73.

Sanders, D. and Y. Zhao, On the entire coloring conjecture, Canad. Math. Bull., 43 (2000) 104-114.

Thomassen, C., Every planar graph is 5-choosable, J. Comb. Theory B, 62 1994) 180-181.

Thomassen, C., Grötzsch's 3-color theorem, J. Comb. Theory B, 62 (1994) 268-279.

Thomassen, C., 3-list coloring planar graphs of girth 5, J. Comb. Theory B, 64 (1995) 101-107.

Voigt, M., List colourings of planar graphs, Discrete Math., 120 (1993) 215-219.

Voigt, M. and B. Wirth, On 3-colorable non-4-choosable planar graphs, J. Graph Theory, 24 (1997) 233-235.

Wagner, K., Über zwei Sätze der Topologie: Jordanscher Kurvensatz und Vierfarbenproblem, Doctoral Dissertation, Köln; supervisor, Karl Dörge, 1935.

Wagner, K., Bemerkungen zum Vierfarbenproblem, Jahresber. Deutsch. Math. Verein., 46 (Pt. 1) (1936) 26-32.

Wagner, K., Ein Satz über Komplexe, Jahresber. Deut. Math. Verein., 46 (Pt. 2) (1936) 21-22.

Wagner, K., Zwei Bermerkungen über Komplexe, Math. Annalen, 112 (1936) 316-321.

Wagner, K., Über eine Eigenschaft der ebenen Komplexe, Math. Annalen, 114 (1937) 570-590.

Wagner, K., Über eine Erweiterung eines Satzes von Kuratowski, Deutsche Math., 2 (1937) 280-280.

Wagner, K., Bermerkungen zu Hadwigers Vermutung, Math. Annalen, 141 (1960) 433-451.

Wagner, K. Beweis eine Abschwächung der Hadwiger-Vermutung, Math. Annalen, 153 (1964) 139-141.

Waller, Simultaneously colouring the edges and faces of plane graphs, J. Combin. Theory B, 69 (1997) 219-221.

West, D., Introduction to Graph Theory, Second Edition, Prentice-Hall, Upper Saddle River, 2001.

Wilson, R., Graphs Colourings and the Four-colour Theorem, Oxford, Oxford, 2002.

Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials.


  1. Introduction
  2. Basic ideas
  3. Face colorings
  4. Vertex colorings
  5. Some history
  6. References

Welcome to the
Feature Column!

These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Read more . . .

Search Feature Column

Feature Column at a glance


Show Archive

Browse subjects



Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia