Problem of the Week
Hilton Memorial Lecture
That planar maps can be properly colored in four colors was conjectured in 1852 by Francis Guthrie, then a recent student at University College, London. This, being easily understood and resistant to proof, became a challenge to both professional and amateur mathematicians and was finally proved by Appel, Koch and Haken in 1976. In 1989 a more complete version of their proof was published in a 741 page book “Every Planar Graph is Four Colorable”, by Appel and Haken. Clearly, the challenge remained and to this day remains in essence, for all variations of this proof require calculations outside human capabilities of endurance or credible accuracy. In 1993/94 joint work with Sanders, Seymour and Thomas managed to obtain a computer assisted proof by considerably more concise methods, which was published in 1997, in a 44 page article leaving out only the computer programs and calculations (which are also readily available). The goal of the later research group was to make it possible to use the four color theorem and its proof techniques in the outstanding open problems of the area. Most basic among these are the Hadwiger k-coloring conjectures and the Tutte dual-coloring conjectures (for nowhere-zero 4-flows and 5-flows). This talk will address the “big picture” of the essence of the available proof methods and the prospects that new mathematics can be produced in the research context of the 4-color problem.