Colorful Mathematics: Part I
5. Some history
Kempe's argument was so convincing that it was quite a few years before Percy Heawood noticed that it was incorrect. Kempe's approach reduced the problem to coloring the faces of 3-valent plane maps. The key idea of the proof involved is what are known today as Kempe chains. Suppose that one is coloring a map and one has a 4-sided region R which has faces which have been already colored with the four colors available. Kempe wanted to be able to recolor the map so that the coloring rule was met but that R could be colored. Suppose the colors (a, b, c, and d) around the region R are as represented in the diagram below:
Now consider all the regions that are colored b and d. Either there is a chain of b- and d-colored regions that connect region 4 and region 2, or no such chain exists. If no such chain exists, we can interchange the colors of region 4 and those regions to which it is connected in the d-b color chain, leaving region 2 colored by b. This color interchange colors region 4 with b. Now, region 4 and region 2 are colored b and we have the neighbors of R using only three colors, so that we can use the 4th color (b) for region R. In the case that there is a chain of d- and b-colored faces from region 2 to region 4, we can be assured, by a simple topological result following from the Jordan Curve Theorem, that there can be no chain of a- and c-colored faces from region 1 to region 3. Thus, arguing as we did above, we can free up a color to use on region R. Kempe chains can be adapted to apply in the vertex coloring version of the 4-color problem.
The genus of a surface with positive genus g can be thought of as a sphere with g handles attached. You can think of a surface with genus 1 as a donut (torus with 1 hole) and a surface with genus 2 as a donut with two holes. Eventually, in 1968 G. Ringel and J.W.T. Youngs showed that one can replace the inequality above with an equality. The issue of the chromatic number for maps on surfaces with negative genus (unorientable surfaces) has also been accomplished; all this, before the four-color problem, which emerges from the formula above when g is set to be zero, was settled! Thus, Heawood formulated ideas that have kept people interested in coloring problems busy to the present day. Not only did he make important contributions to graph-coloring problems, but he is famous for his devotion to overseeing repairs to Durham Castle in England, which had, due to neglect, developed structural problems. Heawood helped to ensure that it was restored to its former glory.
Welcome to the
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.
Search Feature Column
Feature Column at a glance