Skip to Main Content

Colorful Mathematics: Part IV

Feature Column Archive

6. 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.

Cozzens, M. and F. Roberts, T-colorings of graphs and the channel assignment problem, Congr. Numer. 35 (1982) 191-208.

Cozzens, M. and D.-I. Wang, The general channel assignment problem, Congr. Numer. 41 (1984) 115-129.

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

Hale, W., Frequency assignment: theory and applications, Proc. IEEE 68 (1980) 1497-1514.

Hale, W., Frequency assignment methodology: an annotated bibliography, NTIA-SP-80-10, N.T.I.A., Institute for Telecommunication Sciences, Boulder, CO, 1980.

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 Hanover. (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.

Opsut, R. and F. Roberts, On the fleet maintenance, mobile radio frequency, task assignment, and traffic phasing, in G. Chartrand, Y. Alavi, D. Goldsmith, L. Lesniak-Foster, and D. Lick, (eds.), The Theory and Applications of Graphs, Wiley, New York, 1981, pp. 479-492.

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.

Roberts, F., T-colorings of graphs: recent results and open problems, Discrete Math. 93 (1991) 229-245.

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.

Tesman, B., T-colorings, list T-colorings, and set T-colorings of graphs, PH.D., Thesis, Department of Mathematics, Rutgers University, New Brunswick, October, 1989.

Tesman, B., Applications of forbidden difference graphs to T-coloring, Congr. Numer. 74 (1990) 15-24.

Tesman, B., set T-colorings, Congr. Numer. 77 (1990) 229-242.

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.

Wang, D.-I., The channel assignment problem and closed neighborhood containment graphs, Ph.D. Thesis, Northeastern U., Boston, MA., 1985.

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. Resolving conflicts (I)
  3. Resolving conficts (II)
  4. From schoolgirls to tournaments
  5. Mathematics and cell phones
  6. References