Colorful Mathematics: Part II
Posted October 2003.
1. Introduction
In 1976, Wolfgang Haken and Kenneth Appel solved a problem that had gone unresolved for over 100 years: Is it true that every map drawn in the plane can be colored with four or fewer colors? The ease of stating the problem belied the proof that Haken and Appel provided, which to this day generates some controversy. The proof depended on the use of a computer program in an essential way. It is impossible for a person to verify every step of the proof. Like many complex proofs, the original version of the proof that Haken and Appel announced had some errors. Although they provided corrections, the fact that the proof also involved a computer added to the discomfort with which the proof was greeted. Subsequently, in 1994 a new proof of the fourcolor theorem appeared. This proof was the work of Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas. Though the proof was considerably simpler than the HakenAppel proof, like that proof it followed an approach pioneered by Heinrich Heesch (19061995). Yet this proof still needed a computer to verify the many cases that arose from the strategy. Some people are skeptical that a truly short proof of the fourcolor problem exists.
Although resolving the fourcolor problem was a triumph of the human intellect, more important are the mathematical tools and ideas that emerged from its solution. New insights into many additional coloring problems emerged, as did powerful new ideas that were useful in answering questions about embeddings of graphs on surfaces. Furthermore, the investigation of coloring problems led to many applications outside of mathematics. These include scheduling of college courses and legislative committees, as well as assigning frequencies for use in cell phone traffic.
Joseph Malkevitch
York College (CUNY)
Email: malkevitch@york.cuny.edu
 Introduction
 Insights into coloring planar graphs
 Edgecolorings
 The Hamilton connection
 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 . . .
Feature Column at a glance
