[讨论]三言两语话四色

雷明85639720

三言两语话四色
雷  明
（二○一一年八月三十一日）
图的色数是把图中相邻顶点都着以不同颜色时，图中所用的最少颜色数。
把图的所有顶点划分到不同的几个子集合里，使得每个子集合中的顶点在原图中都是互不相邻的，这就叫图的顶独立集划分。在对任何图的顶独立集划分中，总存在着一个顶独立集数目是最少的划分，把这个顶独立集数是最少的划分中的顶独立集数，就叫图的最小顶独立集数。由于顶独立集内的顶点都是不相邻的，同一独立集内的顶点着同一颜色是完全可以的，所以说任何图的色数就等于其最小的顶独立集数。
任何图都可以通过同化运算得到其最小的完全同态，由于该完全同态的每一个顶点均是由不相邻的顶点同化而来的，即实质上该完全同态的每一个顶点就代表着一个顶独立集，所以说图的最小完全同态的顶点数也就等于图的最小顶独立集数，同样也有图的色数等到于图的最小完全同态的顶点数。
任何图中都至少有一个最大团，该团的顶点数就是图的密度。最大团外的一条道路最大可能只可能有一个顶点同化不到最大团中去，而多条有联存在的上述道路，则就有多个顶点同化不到最大团中去，但这种有联存在的道路的条数是受到图的密度而限制和制约的，不可能无限的增多。这个限制是有联存在的上述道路的条数不会大于图的密度的一半，也即任何图同化时最大可能只可能有不多于其密度一半的顶点同化不到最大团中去。这就决定了任何图的最小完全同态的顶点数也一定是小于等图的密度的一倍半。
因为图的色数是等于其最小的顶独立集数，也等于其最小完全同态的顶点数，所以也就有任何图的色数一定是不会大于其密度的一点五倍的结论。
平面图的密度不大于4。对于密度不大于3的图，从上式可以看出，其色数一定是小于等于4的；但对于密度等于4的图，则有可能其色数将是大于4的，但可以很容易的检验出在这种情况下的图一定不是平面图。这就证明了任何平面图的色数均不大于4的四色猜测是正确的。
由于平面图的对偶图仍是平面图，对偶图中的顶点就是原平面图中的面，对平面图的面着色也就相当于对其对偶图的顶点着色。平面图顶点着色的色数不大于4，那么平面图面着色的色数也一定不会大于4。地图实质上就是一个平面图，且是3—度正则的，地图着色就是对其中面（区域）的着色，所以任何地图的色数也一定是不会大于4的。这也就证明了地图的四色猜则是正确的。
上面说的只是图的顶点着色，对于图的边着色来说，由于其线图的密度ω线等于原图的最大度Δ，所以图的线色数的界是：Δ≤γ线 ≤＜1.5Δ＞；对于图的顶点和边的全着色来说，由于其全图的密度ω全等于原图的最大度Δ加1，所以图的全色数的界是：Δ＋1≤γ全 ≤＜1.5（Δ＋1）＞； 由于线图和全图都是原图的图值函数，所以有图值函数的色数的界是：ω图值函数≤γ图值函数≤＜1.5ω图值函数＞（＜ ＞表示其中的数字向下取整，因为任何图的色数一定是整数）。
以上所说的具体的证明方法，均请见本人在《数学中国》网上发表过的有关文章，或见本人的博客。

雷  明
二○一一年八月三十一日于长安

注：此文已于二○一一年十月十三日在《数学中国》网上发表。