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

点击翻译按钮获取中文摘要

ABSTRACT for FRG award DMS-035472, DMS-0354465 and DMS-0354554 of Thomas, Seymour and RobertsonWe propose to study the four-colour problem and its extensions. The four-colour problemitself was proposed as a conjecture in the the mid-19th century, and remained open forover 120 years, until it was settled by Appel and Haken in 1977. That period coincidedwith the birth of graph theory as a serious subject, and graph theory grew up aroundthe various attempts to settle the four-colour problem. The problem lives right at theheart of modern graph theory, and still is not properly understood.In particular, the proof by Appel and Haken used a computer, and for a mathematiciantrying to understand what makes a result true, this is not acceptable; it may beconvincing 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,3this is easy, and when k = 4 this is equivalent to the four-colour problem; and we proved thatit 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.