FRG: Collaborative Research: The Four-Color Theorem and Beyond

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

ABSTRACT for FRG award DMS-035472, DMS-0354465 and DMS-0354554 of Thomas, Seymour and Robertson We propose to study the four-colour problem and its extensions. The four-colour problem itself was proposed as a conjecture in the the mid-19th century, and remained open for over 120 years, until it was settled by Appel and Haken in 1977. That period coincided with the birth of graph theory as a serious subject, and graph theory grew up around the various attempts to settle the four-colour problem. The problem lives right at the heart of modern graph theory, and still is not properly understood. In particular, the proof by Appel and Haken used a computer, and for a mathematician trying to understand what makes a result true, this is not acceptable; it may be convincing evidence that the result is true, but it is not helpful for understanding. We already found our own proof (joint with Sanders), and our proof is simpler and more easily checked than the Appel-Haken proof, but it too uses a computer. We plan to redesign the proof to reduce the dependence on computers as far as we can. There are a number of proposed extensions of the four-colour theorem, mostly still open. For instance, there is Hadwiger's conjecture of 1943 that every graph that cannot be coloured with k colours can be contracted to a complete graph on k+1 vertices. For k = 1,2,3 this is easy, and when k = 4 this is equivalent to the four-colour problem; and we proved that it is also true for k = 5. We would like to extend this to higher values of k. There are a number of other extensions of the four-colour problem, detailed in the proposal itself; for instance Tutte's 4-flow conjecture, the odd minor conjecture, and Grotsch's conjecture.