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

雷明85639720

[watermark]

任意图色数的确定
雷  明
（二○一二年元月十九日）
1、图的着色是给图的顶点染上不同的颜色，使相邻的顶点不用同一颜色。一个图所用的最少颜色数就是该图的“色数”，用γ表示。
2、图的顶独立集是把图的顶点划分到不同的集合内，使相邻的顶点不被划分到同一个独立集内。一个图所能划分出的最少的独立集个数就是该图的“顶独立集数”，用β表示。
3、从图的着色与图的顶独立集划分以及图的色数与图的顶独立集数的概看，图的顶独立集划分就相当于对图的顶点着色的过程，而图的顶独立集数就是图的色数，即有γ＝β。
4、求图的顶独立集数要用到一种叫做“同化”的图的运算。图的同化运算是把不相邻的顶点凝结为一个顶点的过程，也相当于把该两个顶点划分到同一个顶顶立集之内的过程。图顶点同化的最后结果是一个各顶点都相邻的完全图，叫图的完全同态，其顶点数用α表示。一个图经过一连串的同化后，所得到的顶点数为最少的那一个完全同态的顶点数就是该图的顶独立集数，也就是该图的色数，即有γ＝β＝α。
5、若Kω是一个密度为ω（ω为图中最大团的顶点数）的图中的一个最大团，再若Pn是该最大团外的一条道路。当道路中的非端点顶点都与最大团中的相同的ω－2个顶点相邻，且道路的两个端点顶点又分别与最大团中的ω－1个顶点相邻时，这条道路就叫做“饱和道路”，因为当在道路与最大团间再增任一条边时，图的密度就会变大，或者道路就会变成两条上述的那种道路。这样的饱和道路中的顶点在向最大团同化时，其实质就是该道路向最大团中的某一个K2团的同化。同化的结果有两种情况：一种情况是道路中所有顶点全部都可同化到最大团中去（如图1和图4）；另一种是道中总有一个顶点同化不到最大团中去（如图2和图3），且道路中的每一个顶点都可当作这样的不可同化顶点，其机会是相等的（几个图中只画出了关键的顶点和边，其它均未画出）。

6、在图1 和图2 中，道路的两个端点顶点分别与最大团中的那个K2团的两个顶点相邻，而在图3 和图4 中，道路的两个端点顶点则同时与最大团中的那个K2团的某一个顶点相邻。在图1 和图3中，道路中的顶点数是偶数，而在图2 和图4 中，道路中的顶点数是奇数。若把图中的道路首先同化为一个K2团时，这时的实质就成了一个K2团向最大团中的那个K2团的同化，也会得到与以上同样的结果。除此之外的任何一条不满足上述饱和道路条件的非饱和道路的各个顶点都一定是可以同化到最大团中去的。如果不可同化道路是一条回路即圈时，也可得与上相同的结果。
把总有一个顶点同化不到最大团中去的图2 和图3的两种情况下的道路叫做“不可同化道路”。
7、一条不可同化道路有一个顶点同化不到最大团中去，那么有S条相互有联的不可同化道路就有S个顶点同化不到最大团中去，这是因为有联存在的各条道路中的各个顶点均是相互相邻的，这S个顶点也不可能再同化为一个顶点。如果S条不可同化道路间没有形成联时，则各条道路间一定存在互不相邻的顶点，同化时可以把这些顶点作为同化不到最大团中去的顶点，因为道路中的任何一个顶点都可作为这样的顶点。然后再把这S个不可同化顶点再同化到一起，仍然只相当于只有一条不可同化道路的情况，只有一个顶点未同化到最大团中去。
8、不可同化道路的条数S的值最大是多少，它与图的密度有什么关系呢。由于道路的密度是2，联的密度则是构成联有各条道路的密度之和，则该S 条不可同化道路联的密度是2S，联中的最大团是K2S，这是因为这个最大团是由S条道路各出2个顶点而构成的。由于这个团K2S是图的一个分子图，其顶点数2S只可能小于等于图的密度ω，所以有2S≤ω的关系。即S≤ω/ 2。
9、由于最大团Kω中的顶点是不能再同化的，所以图同化的最小完全同态的顶点数一定是要大于等于图的密度的；又由于S≤ω/ 2，所以最小完全同态的顶点数最大也只能小于等于图的密度的一倍半。即有ω≤α≤1.5ω，因此也有ω≤β≤1.5ω，ω≤γ≤1.5ω。ω≤γ≤1.5ω就是任意图色数的界，它只与图的密度有关，而与图的顶点数关无关系。
10、由于平面图的密度总不大于4，这就可以把一个无穷的问题变成一个有穷的问题。把平面图的密度不大于4代入到任意图色数的界ω≤γ≤1.5ω中，就得到任何平面图着色的色数都不大于4的结论，即γ平面图≤4，这就证明了四色猜测是正确的。这里要注意的是，如果一个密度为4的图中只要有一条饱和道路时，图就成了非平面图，成不是平面图了。所以看上去是乎在密度为4 时有可能色数是大于4 的，但这种情况下的图就不再是平面图了（密度是4的图有些是平面图，有些则是非平面图，密度4是平面图向非平面图过渡的密度值）。因为四色问题研究的对向就只是在平面图范围之内的。

                 雷  明
       二○一二年元月十九日于长安