Skip to Main Content

Colorful Mathematics: Part III

Feature Column Archive

5. References

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

Bodendiek, R. (ed.), Graphen in Forschung und Unterricht, Festschrift K. Wagner, Dad Salzdetfurth: Barbara Franzbecker.

Bogart, K., Discrete Mathematics, Heath, Lexington, MA., 1988.

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.

Brightwell, G., Partial Orders, in Graph Connections, L. Beineke and R. Wilson, (eds.), Oxford Press, Oxford, 1997, pp. 52-69.

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ötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Lther-Univ. Hall-Wittenberg Math.-Natur. Reihe, 8 (1959) 109-120.

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 Naturforschungsgesellschaft Zürich, 88 (1943) 133-142.

Hartsfield, N. and G. Ringel, Pearls in Graph Theory, Revised and Augmented Edition, Academic Press, Boston, 1994.

Heesch, H., Zur systematischen Strukturtheorie III, IV, Z. Krist. 73 (1930) 325-345, 346-356.

Heesch, H., Untersuchungen zum Vierfarbenproblem, Mannheim/Wien/Zürich, Bibliographisches Institute, 1969.

Heesch, H., E-Reduktion, Preprint Nr. 19 des Instituts für Mathematik der Technischen Universität Hannover. (Also, in Bodendiek, Festschrift, Klaus Wagner.)

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

Kronk, H., and J. Mitchem, 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.

Malkevitch, J., Convex isosceles triangle polyhedra, Geombinatorics 10 (2001) 122-132.

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., Färbungsprobleme auf Flächen und Graphen, VEB Deutscher Verlag der Wissenschaften, 1959.

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

Ringel, G., 250 Jahre Graphentheorie, In: Graphen in Forschung und Unterricht: Festschrift K. Wagner, Barbara Franzbecker Verlag, 1985, pp. 136-152.

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.

Schnyder, W., Planar graphs and poset dimension, Order 5 (1989) 333-343.

Schnyder, W., Embedding planar graphs on the grid. Proc. First ACM-SIAM Symposium on Discrete Algorithms, (SODA), 1990, pp. 138-148.

Schnyder, W. and W. Trotter, Convex embeddings of 3-connected plane graphs, Abstracts AMS, 92T-05-135, 1992.

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, Series B, 62 (1994) 268-279.

Thomassen, C., Grötzsch's 3-color thoerem and its counterpart for the torus and projective plane, J. Comb. Theory, Series B, 62 (1994) 268-279.

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

Thomassen, C., A short list color proof of Grötzsch's thoerem, J. Comb. Theory, Series B, 88 (2003) 189-192.

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 of these materials.

  1. Introduction
  2. New problems from old ones
  3. Exotic coloring problems
  4. Breaking the rules
  5. References