研究四色问题三十年之总结

雷明85639720

研究四色问题三十年之总结
雷  明
（二○一四年十二月十七日）

我从一九八五年开始，怀着对所谓电子计算机证明了四色猜测的说法的不满，以及对四色问题的爱好，研究四色问题至今已经整整三十年了。现在总算自我认为有一个满意的结果。有必要作一下小结了，很可能从此再也不去对这一问题进行研究了。
一、我研究四色问题可分为四个阶段
第一阶段是从一九八五年至一九九一年的七年。这一时期，我与其他前辈们一样，也是画图、着色，虽然都能对自已所画的平面图着上不超过四种的颜色，但总觉得还不能说明对于任意的平面图都能进行4—着色，因为自已所着过的图只是平面图中极少的一部分，不能够代表全体。虽然自已经对一八九○年以来不能进行4—着色的赫渥特图进行了4—着色，但也不能因此说明四色猜测就是正确的。
第二阶段是从一九九二年至一九九九年的八年。一九九二年三月八日我在陕西省数学会第七次代表大会暨学术交流会（西安空军工程学院）上提出，解决四色问题还得要从不对任何图着色入手，因为图是无限多的，永远也是着色不完的。从此我开始对图论进行研究，开始了从图论的角度上去对四色猜进行研究的道路。这一阶段我从图的不相邻的顶点可以同化为一个顶点的这一运算入手，研究了图顶点着色的色数与图的密度（图中最大团的顶点数）的关系，得到了任意图的色数的界是大于等于其密度而小于等于其密度的1.5倍的结论。当平面图的密度小于等于3时，其色数都是小于等于4的；当平面图的密度是4时，图中只要存在一条不可同化道路（该道路上总有一个顶点是不能同化到与其邻接的最大团中去），图就成了非平面图，就不再是四色问题研究的对象了，所以密度是4的平面图的色数也是不大于4的。这也就证明了四色猜测是正确的。
第三阶段是从二○○○年到二○一一年的十二年。这一阶中，二○○五年前的六年，基本上是对自已用图论的方法证明四色猜测进行完善，在研究方面没有什么进展；二○○五年后的六年，除了开始编写自已的研究成果外，主要是在网上与同行爱好者们进行交流。有友好交流的时候，也有激烈辨论的时候。这一时期除写了八十多万字的科普读物《四色问题与欧拉公式》外，在网上还写了累计大约有二百万字的大量的博文，与网友们进行交流和辨论。
第四阶段是从二○一二年到二○一四年的三年。二○一二年我参加了第五届全国组合数学与图论大会（洛阳师范学院），并作了学术论文报告。会后有厦门大学的杨卫华博士很关心我的研究，但对我提出了一个问题。说从米歇尔斯基操作（以下简称M—操作）可以得到不含三角形但色数是任意大的图，说明图的色数是无界的。并指出我认为的任意图的色数有界是错误的，并由此推得我对四色猜测的证明也就是错误的。我又通过对米歇尔斯基操作的研究，认为除了K1，K2（P2），K3（C3），P3外，其他的任何平面图进行了一次M—操作后均是非平面图，都不是四色问题研究的对象了，而以上这几个图在再进行一次的M—操作后也都成了非平面图。说明M—操作对证明四色猜测是不会产生影响的。
这一阶段，我还对拓朴学进行了研究，研究了多阶曲面上的图的着色问题。第一、二、三阶段我的研究只是在平面图与非平面图中进行的，是以图的密度为图的基本参数的；后来我研究了拓朴学后，研究的是多阶曲面上的图的着色，是以曲面或图的亏格为基本参数的。并能从已经证明是千真万确的、同样是适合于亏格为0的平面图的多阶曲面上图的欧拉公式中，可以直接推导出赫渥特给出的多阶曲面上的地图着色公式，把亏格为0的平面图的亏格0代入其中，可以得到任何平面图的色数都不大于0的结论。四色猜测是正确的。达到了我在一九九二年提出的不画任何图，也不给任何图着色，就可以证明四色猜测的目的。下面我简要叙述于后：
二、我用拓朴学研究四色问题的主要内容
图中不相邻的顶点可以着同一种颜色；不相邻的顶点可以同化成一个顶点（把不相邻顶点凝结成一个顶点的过程叫同化）；不相邻的顶点可以划分到一个顶独立集内。
任何一个图同化到最后，一定可以得到一个顶点数不能再少的最小完全同态，即一个完全图；这个完全图同态的各个顶点都要代表着原图中的若干个不相邻的顶点，这些不相邻的顶点着同一颜色当然是可行的；该最小完全同态的顶点数也就是图的最小的顶独立集数；由于完全图的色数就等于其顶点数，所以就有任意图的色数＝其最小完全同态的顶点数＝其最小的顶独立集数的关系。
任何一个图同化的最后结果——最小完全同态的亏格一定是小于等于原图的亏格的。完全同态也是一个完全图，完全图也是一个图，那么它也一定适合于多阶曲面上的图的欧拉公式v＋f－e＝2－2n（其中v、f、e、n分别是图的顶点数、面数、边数和亏格数）。把任意图中边与面的关系3f≤2e中的f＝2e/3代入欧拉公式中得
     3v－e≥6＋6n
再把完全图的边与顶点的关系e＝v（v－1）/2代入上式中即可得到
        7v－v2－12＋12n≥0
即有
        v2－7v＋12－12n≤0
解这个关于v的一元二次不等式就得到任意图的最小完全同态的顶点数
        v≤（7＋√（1＋48n））/2
式中的等式是最小完全同态的亏格与原图亏格相同的图的最小完全同态的顶点数，不等式则是最小完全同态的亏格小于原图亏格的图的最小完全同态的顶点数。由于图的顶点数是正整数，所以上式还得向下取整得
        v≤＜（7＋√（1＋48n））/2＞
再由于完全图（或图的最小完全同态）的色数就等于其顶点数，所以上式还可写成
        γ≤＜（7＋√（1＋48n））/2＞
这就是赫渥特在一八九○年给出的多阶曲面上的地图着色公式。
上式中当n＝1时，γ≤7，K3，3，K5，K6，K7的亏格都是1，其最小完全同态分别是K2，K5，K6，K7，其顶点数分别是2，5，6，7，色数也就分别是2，5，6，7，都是小于等于7的；当上式中图的亏格n＝0时，γ≤4，这就证明了四色猜测是正确的。例如K1（点），K2（线段），K3（三角形），K4（正四面体），Pn（道路或树），C2n（偶圈），C2n－1（奇圈），L2n（偶轮，偶棱锥体），L2n－1（奇轮，奇棱锥体），正六面体（偶棱台柱），寄棱台柱，正八面体（偶菱体），寄菱体，正十二面体，正二十面体等的亏格都是0，它们的最小完全同态分别是K1，K2，K3，K4，K2，K2，K3，K3，K4，K2，K3，K3，K4，K3，K4，其顶点数分别是1，2，3，4，2，2，3，3，4，2，3，3，4，3，4，都是没有大于4 的。实际上赫渥特的多阶曲面上的地图着色公式只给出了一个在某亏格下的图的色数的界，并不是直接给出了某个图的具体色数。

雷  明
二○一四年十二月十七日于长安

该文已于二○一四年十二月十七日在《中国博士网》发表过。