四色问题

[拼音]：sise wenti

[外文]：four color problem

又称四色猜想，数学中的著名问题之一。1852年F.格思里提出如下猜想：对平面或球面上的任一地图着色，至多用四种颜色就可以使两个相邻(即有一段公共边界)的国家或区域的颜色不相同。1890年，A.B.肯普和P.D.希伍德证明了五色定理：对平面上的任何地图着色，用五种颜色就可以使得任何两个相邻的区域具有不同的颜色。

对平面上的任何地图，若用点表示区域，用边表示区域的相邻关系，则得到一个对应的平面图(见图论)，如图1

。于是，四色问题即为任何平面图的点色数不超过4的问题。

一个平面图G，若对G中任意两个不邻接的点u、υ加进边(u，υ)后就不是平面图，则G 称为极大平面图。如果能证明所有极大平面图的点色数不超过4，那么，所有平面图的点色数也不超过4，因此四色问题中所研究的平面图都假定是具有足够多点数的极大平面图。点数小于96时，可用推理方法直接证明四色定理。

一个平面图，若它的每个有界面的边界都是三角形，则称之为构形。一个构形F，若具有下述性质，则称F为可约的：对任何极大平面图G，若G中包含F，则存在G的一个子图G′(通常G′是从G中去掉F内部的点后而得到的)，使G的色数等于G′的色数。例如，若平面图G中含有图2

中的构形p，取子图G′= G-υ4，只要用与υ1，υ2，υ3的染色不同的第4种颜色去染υ4，就可从G′的四色着染导出G中的四色着染，因此构形p是可约的。一个由有限个构形组成的集合F，若具有下述性质，则称F为一个不可免完备集：任何点数多于4的极大平面图，至少包含F中的一个构形。已经证明，图2中的构形集{p，Q，R}组成一个不可免完备集，且p、Q是可约的。假如能继续证明R也是可约的（即如果{p，Q，R}是一个由可约构形所组成的不可免完备集），那么，应用数学归纳法就可证明四色猜想。然而，至今未能得证。1879年，A.B.肯普认为他已证明了四色猜想，但他的证明是错的，其原因在于承认了R具有可约性。

1913年，G.D.伯克霍夫发现了一些新的可约构形。20世纪30年代，H.希施企图用电子计算机在可约构形中找出一个不可免完备集。他提出了一个检查给定的构形集合，是否为不可免完备集的算法。1971年有人声称借助计算机找出了一个不可免完备集，其中的构形全是可约的。但H.惠特尼和W.T.塔特独立地发现其错误是计算机误算出一个构形的可约性。同时，他们提出了可约性的分类理论。1976年K.I.阿佩尔和W.哈肯改进了希施的算法，并研究了可约构形的范图，他们声明利用电子计算机找到了一个由1936个可约构形所组成的不可免完备集，从而在美国数学会通报上宣布证明了四色猜想。之后，减少到1834个可约构形。

与四色问题有关的命题很多。例如，赫德维格尔猜想：凡是点色数为x的图，都可通过一系列减去边或将一个边压缩成一个点的方式变成一个 x个点的完全图。已经证明，当x≤4时，命题成立；而x=5时该猜想与四色问题等价。四色问题对图的着色理论、平面图理论、代数拓扑图论、极图理论以及有限射影几何的发展，都起了推动作用。

参考书目

The Four Colour Problem