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

对于Thomas， Seymour和robertson的FRG奖DMS-035472， DMS-0354465和DMS-0354554，我们提出研究四色问题及其扩展。四色问题本身是在19世纪中期作为一个猜想提出的，并且一直存在了120多年，直到1977年由Appel和Haken解决。那个时期与图论作为一门严肃学科的诞生相吻合，图论是围绕解决四色问题的各种尝试而发展起来的。这个问题是现代图论的核心，但仍然没有得到正确的理解。特别是，阿佩尔和哈肯的证明使用了计算机，对于一个试图理解是什么使结果为真的数学家来说，这是不可接受的；它可能成为结果是真实的令人信服的证据，但它对理解没有帮助。我们已经找到了自己的证明（与Sanders联合），我们的证明比apple - haken证明更简单，更容易检查，但它也使用了计算机。我们计划重新设计证明，以尽可能减少对计算机的依赖。有许多关于四色定理的扩展，大多数仍然是开放的。例如，1943年的Hadwiger猜想，每个不能用k种颜色着色的图都可以缩并成一个有k+1个顶点的完全图。对于k = 1,2,3，这很简单，当k = 4时，这等同于四色问题；我们证明了k = 5时也是成立的。我们希望将其扩展到k的更高值。四色问题还有许多其他的扩展，在提案本身中详细说明；比如Tutte的四流猜想，奇次猜想，还有Grotsch的猜想。

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.