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

摘要对于Thomas、Seymour和Roberson的FRG奖DMS-035472、DMS-0354465和DMS-0354554，我们建议研究四色问题及其推广。四色问题本身是作为一种猜想在19世纪中叶提出的，并持续了120多年，直到1977年阿佩尔和哈肯解决了这个问题。这一时期恰逢图论作为一门严肃学科的诞生，图论围绕着解决四色问题的各种尝试而发展起来。这个问题存在于现代图论的核心，至今仍未得到很好的理解。特别是，阿佩尔和哈肯的证明使用了计算机，对于试图理解结果为真的原因的数学家来说，这是不可接受的；它可能是证明结果为真的有说服力的证据，但它无助于理解。我们已经找到了自己的证明(与桑德斯联合)，我们的证明比阿佩尔-哈肯证明更简单、更容易检验，但它也使用计算机。我们计划重新设计证明，以尽可能减少对计算机的依赖。有许多对四色定理的建议扩展，大多数仍然是开放的。例如，1943年的Hadwiger猜想，每个不能被k-色染色的图都可以收缩为k-1个顶点上的完全图。对于k=1，2，3，这很容易，当k=4时，这等同于四色问题；我们证明了当k=5时，这也是正确的。我们想把它推广到更高的k值。四色问题还有许多其他的扩展，如图特的4流猜想，奇数小猜想和格罗奇猜想。

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.