Four Color Theorem

Around 1998 Paul Kainen and I worked on an approach to the Four Color Theorem. He is a co-author of a book on this topic reprinted by Dover Publications.
 AUTHOR       Saaty, Thomas L.
 TITLE        The four-color problem : assaults and conquest / Thomas L. Saaty
                and Paul C. Kainen.
 PUBLISH INFO New York : Dover Publications, 1986.
 DESCRIPT'N   vi, 217 p. : ill. ; 21 cm.
 NOTE         Includes bibliographical references (p. 197-211) and index.
 SUBJECTS     Four-color problem.
 LC NO        QA612.19 .S2 1986.  DEWEY NO     511/.5 19.
 OCLC #       12975758.  ISBN         0486650928 (pbk.) : $6.00.

 AUTHOR       Saaty, Thomas L.
 TITLE        The four-color problem : assaults and conquest / Thomas L. Saaty
                and Paul C. Kainen.
 PUBLISHER    New York : McGraw-Hill International Book Co., c1977.
 DESCRIPTION  ix, 217 p. : ill. ; 25 cm.
 NOTES        Bibliography: p. 197-211.  Includes index.
 OCLC NO.     3186236.  ISBN         0070543828 : $23.00.
We take a pair of triangulations of a polygon and four color the vertices such that no two of the same color are connected by an edge of the triangulations. Polygon triangulations are easy to represent using data structures and the topological considerations of planarity are avoided. This turns the problem into a combinatorial one. The planarity reduces to circular order along the polygon and the non-crossing of diagonals. The history of this approach going back to Hassler Whitney and other references to this approach are in the book.

The MacTutor History of Mathematics archive at Saint Andrews has a nice article on the four colour theorem. A summary of a new proof of the four color theorem is at Georgia Tech for which programs and data supplements are available by FTP. A survey (in PostScript) of the paper "The Four-Colour Theorem" is there also.

An elementary introduction to the subject is at The Most Colorful Math of All area of the MegaMath site. Another introduction to Graph Coloring is at the Geometry Center. There is an archive on Graph Coloring Problems in Denmark.

The topic of graph coloring has gotten increasing attention for several reasons. One is the connection with knot theory and statistical physics. A recent reference to this is "Map Coloring and the Vector Cross Product" by Louis H. Kauffman in Journal of Combinatorial Theory B 48(1990)145-154. Other work by Kauffman mentions map coloring and knot theory.

Back to my home page
Last Updated Tue Mar 25 13:03 EST 2003
Michael Somos <>