[原创]任意图顶点着色色数的确定

雷明85639720

[watermark]

任意图顶点着色色数的确定
雷  明
（二○一二年六月十七日）
关键词：图  着色  顶独立集  完全同态  同化  四色猜测
摘  要：证明了四色猜测是正确的
1、几个概念
1、1 图是由顶点与某些顶点间的连线（边）所构成的集合。
1、2 图顶点的着色：给图的顶点着以不同的颜色，使得相邻的顶点不着同一颜色。这里的关键是相邻顶点不能着同一颜色。图中所用的最少颜色数叫做该图顶点着色的色数，用γ表示。
1、3 顶独立集划分：把图的顶点划分到不同的集合内，使得相邻的顶点不被划分到同一个顶独立集内。这里的关键是相邻顶点不能划分在同一个独立集内。一个图所能划分出的最少的顶独立集的个数，叫做该图的最小顶独立集数，用β表示。
1、4 图的同化运算：把图中不相邻的顶点，凝结为一个顶点的过程叫图顶点的同化。这里的关键是相邻顶点不能同化到一起去。每同化一次所得到的图，叫做图的一个同态，一个图经若干次同化后，最终得到的结果一定是一个完全图，这叫做图的完全同态。其中顶点数最少的那一个完全同态就叫某图的最小完全同态。最小完全同态的顶点数用α表示。
由此可以看出：
图顶点着色的色数γ
＝图的最小顶独立集数β
＝图的最小完全同态Kω的顶点数α
由于图中的最大团各顶点是两两均相邻的，不可能再进行同化，所以最小完全同态的顶点数α一定不会小于图的密度ω（图的密度就是图中最大团Kω的顶点数），所以又有
γ＝β＝α≥ω                                    （1）
2、任意图顶点着色色数的界
请看下面两个图的同化过程。这两个图都不是具体的图。图中最大团Kω外的一条道路Pn的每一个顶点都与最大团Kω中未画出的那ω－2个顶点相邻（相邻的边在图中也未画出），道路的两个端点顶点又与最大团中剩余的那个K2团的两个顶点相邻。若在这条道路与最大团间再任增加一条边，将会导致图的密度发生变化（或者道路就会变成两条具有上术性质的道路，道路的长度就会变短），所以把这样的道路就叫做饱和道路。

图1中，在饱和道路Pn中，当n为奇数时，Pn中总有一个顶点同化不到最大团Kω中去，否则n为偶数时，Pn中的顶点则可全部同化到最大团Kω中去。图2 中，同样也在饱和道路Pn中，当n为偶数时，Pn中也总有一个顶点同化不到最大团Kω中去，否则n为奇数时，Pn中的顶点也可全部同化到最大团Kω中去。
道路的种类：
1、普通道路，可以证明该道路一定可以同化到最大团中去；
2、饱和道路，以上图1 和图2 中的道路就是饱和道路。该类道路又可分为两类：
1、可同化道路，这种道路也是可以同化到最大团中去的；
2、不可同化道路，在这种道路上总有一个顶点同化不到最大团中去。
可以证明，当不可同化道路是回路（圈）时，同样也有与以上两图的两种情况完全相同的结论。
如果有S条不可同化道路，且这S条道路构成了联时,就有S个顶点同化不到最大团中去，这S个顶点因其本来在联中就是相邻的，不可再同化在一起，所以有α＝ω＋S。
由于联的密度是构成联的各图密度的和，又因为道路的密度是2,所以该联的密度是就2S。因为该联只是图的一个分子图，其密度一定不会大于图的密度，所以又有2S≤ω,即S≤ω/2。又因为S必须是整数，所以还要向下取整，即又有
S≤                    （2）
因此就有图的最小完全同态的顶点数的界是：
ω≤α≤ω＋＝                 （3）
因此又有
ω≤γ＝β＝α≤                （4）
所以说任意图顶点着色色数的界是
ω≤γ≤                     （5）
    3、四色猜测的证明
由于平面图的密度都不大于4，所以这就使得对于图的密度ω来说的无穷问题就变成了一个有穷的问题了。
把平面图的密度从1 到4 一个个的代入到以上的任意图色数的界的公式中，就可得到任何平面图的色数都不会大于4，即有
        γ平面图≤4          （6）
色数大于4 、密度是4 的图已不再是平面图了（证明略）。
这就证明了平面图的四色猜测是正确的。
奇圈中的每一个K2团外都有一条不可同化道路，所以圈的密度虽是2,但奇圈的色数却是3，等于ω＋1；同样的奇轮中的每一个K3团外都有一条不可同化道路，所以轮的密度虽是3,但奇轮的色数却是4，也等于ω＋1。
4、图值函数顶点着色色数的界
有了任意图顶点着色色数的界，研究图的线色数、全色数以及图的任何图值函数的色数就方便得多了。
比如线图的密度等于原图中的最大度Δ，所以图的线色数就是其线图的色数，其界是
        Δ≤γ线≤           （7）
这就是1964年V•G•Vizing给出的线色数的界，但公式（7）比其更加完善。当时V•G•Vizing给出的线色数的界是Δ≤γ线≤Δ＋1,且只有在Δ等于2和3 时才是正确的。
又比如全图的密度等于原图中的最大度Δ加1,所以图的全色数就是其全图的色数，其界是
Δ＋1≤γ全≤               （8）
这也就是1965年Behzad提出的全色数的猜想，同样公式（8）也比其更加完善。当时Behzad提出的全色数的猜想是Δ＋1≤γ全≤Δ＋2，也只是在Δ等于2 和3时才是正确的。
若给一个图G,其图值函数为f（G），f（G）的密度ωf（G）是与图G的有关参数有关的函数（如ω线＝Δ原图），则图值函数f（G）的顶点着色色数的界是
    ωf（G）≤γf（G）≤      （9）
以上的线图和全图都是原图的图值函数，其色数（也就是原图的线色数和全色数）就是这样得来的。
由于平面图的对偶图也是原图的图值函数，给平面图的面上的着色就相当于对其对偶图的顶点着色，因其对偶图仍是一个平面图，所以原图的面色数也是
γ平面图≤4               （10）
地图着色也是给平面图（地图本身就是一个3—正则的平面图）的面的着色，所以这也就证明了地图的四色猜测也是正确的。
5、结论：四色猜测是正确的
本文没有对任何一个着色，只从图的色数等于图最小完全同态的顶点数着手，得出了最小完全同态的顶点数与图的密度间的关系，进而得到任意图顶点着色色数的界，把平面图的密度不大于4的特点代入其中，就得到了任何平面图着色的色数都不大于4的结论，从而也就证明了四色猜测是正确的。

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