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

摘要针对托马斯、Seymour和Robertson的FRG奖DMS-035472、DMS-0354465和DMS-0354554，我们提出研究四色问题及其扩展。四色问题本身在世纪中期作为一个猜想被提出，并持续了120多年，直到1977年由阿佩尔和哈肯解决。这一时期恰逢图论作为一门严肃学科的诞生，而图论则是围绕着解决四色问题的各种尝试而发展起来的。这一问题是现代图论的核心，至今仍未得到正确的理解。特别是阿佩尔和哈肯的证明使用了计算机，对于一个试图理解是什么使结果为真的数学家来说，这是不可接受的;这可能是证明结果正确的有力证据，但对理解没有帮助。我们已经找到了自己的证明（与Sanders联合），我们的证明比Appel-Haken证明更简单，更容易检查，但它也使用计算机。我们计划重新设计证明，以尽可能减少对计算机的依赖。四色定理有许多被提出的扩展，大多数仍然开放。例如，Hadwiger的猜想1943年，每个不能用k种颜色着色的图可以收缩为k+1个顶点的完全图。对于k = 1，2，3，这是容易的，当k = 4时，这等价于四色问题;我们证明了k = 5时也是如此。我们想把它扩展到更高的k值。四色问题还有一些其他的扩展，在提案本身中有详细说明;例如Tutte的4流猜想，奇未成年人猜想，和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.