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

Michael Somos <michael.somos@gmail.com>

WWW URL: