四色猜测的证明越来越简单

雷明85639720

四色猜测的证明越来越简单
雷  明
（二○一四年十二月十六日）

图顶点着色时不相邻的顶点可着同一颜色。在同化时可以把不相邻的顶点同化成一个顶点。任何图同化的最终结果，都会得到一个顶点数少得不能再少的最小的完全同态（是一个完全图）。最小完全同态的每一个顶点都代表着图中可着同一颜色的若干个互不相邻的顶点，所以这个最小完全同态的顶点数就是该图顶点着色的色数。图中互不相邻的顶点可构成图的一个顶独立集，那么该最小完全同态的顶点数也就是该图的最小顶独立集数。同一个顶独立集内的顶点是互不相邻的，着同一颜色是完全可以的。
这样以来，我们可以把求图顶点着色的色数变成求图的最小完全同态的顶点数的问题。我们已经知道图的最小完全同态的亏格是小于等于图的亏格的（如K3，3和K5的亏格都是1，其最小完全同态分别是K2和K5，而K2和K5的亏格却分别是0和1，但它们都是小于等于1的），所以，相同亏格的图，最小完全同态的顶点数是不一定相同的。
完全同态是一个完全图，完全图也是一个图，所以也一定是适合于多阶曲面上图的欧拉公式v＋f－e＝2－2n的。由于在任何图中都有3f≤2e的关系，把f≤2e/3代入v＋f－e＝2－2n中得
    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＝0时，γ≤4，这就证明了四色猜测是正确的。在v≤（7＋√（1＋48n））/2中，图的亏格n在变化求图的最小完全同顶点数v，反过来，若让图的最小完全同态的顶点数v进行变化，而求图的最小完全同态或完全图的亏格n时，则可对上述关于v的一元二次不等式进行因式分解得
        （v－3）（v－4）≤12n
再变形得
        n≥（v－3）（v－4）/12
由于图的亏格是正整数，所以上式还要向上取整得
        n≥［（v－3）（v－4）/12］


又由于图的亏格是其所能嵌入的曲面的最小亏格，所以顶点数是v的完全图的亏格n则是
        n＝（v－3）（v－4）/12
这就是杨斯提出的完全图的亏格的计算公式。由于赫渥特的地图着色公式和杨斯的完全图的亏格算公式都是从同一个一元二次不等式得来的，所以该两个公式是可以相互推导出来的。读者自已可以推导一下。

                         雷  明
二○一四年十二月十六日于长安注：该文已于二○一四年十二月十六日在《中国博士网》上发表过。