图的色数不大于图的密度的1.5倍

雷明85639720

图的色数不大于图的密度的1.5倍
雷  明
（二○一五年四月二十八日）

任何图中必有一个顶点数最多的最大团，该团的顶点数就叫该图的密度（用字母ω表示）。图同化时若在一条道路上总有一个顶点同化不到最大团中去，则该道路对于该最大团来说就是一条不可同化道路。对于同一个最大团来说，若存在相互间都有联的S条不可同化道路，则这些道路的联中的最大团的顶点数一定是2S，因为这个团只是图中的一个分子图，所以该团的顶点数最多只能与图中的最大团的顶点数相等，因此有2S≤ω，也有S≤ω/2。有S条不可同化道路，就有S个顶点同化不到最大团中去，图同化最终的最小完全同态的顶点数一定是小于等于ω＋ω/2＝1.5ω的，欺负色数也是小于等于1.5ω的。
平面图的密度只有1～4四种，这就使得一个对于图的密度来说是无穷的问题变成了一个有穷的问题。当图的密度ω＝1时，该图着色时一种颜色一定够用了。当ω＝2，图中还含有5—圈以上的寄圈时，圈中相邻的两个顶点就是一个最大团，圈中其他的顶点则构成了该最大团的一条不可同化道路，其条数是S＝1，该图着色时用ω＋S＝2＋1＝3种颜色也就够用了，不大于密度2的1.5倍3；若不含寄圈时，有两种颜色就够用了。当ω＝3，图中还含有5—轮以上的寄轮时，轮中相邻的两个轮沿顶点与轮的中心顶点也就是一个最大团，轮中其他的轮沿顶点则构成了该最大团的一条不可同化道路，S＝1，该图着色时用ω＋S＝3＋1＝4种颜色也就够用了，也没有大于密度3的1.5倍4.5；不含寄轮时，3种颜色也就够用了。当ω＝4时，似乎其色数可能有大于4 的情况，但对于图中某个最大团K4来说只要有一条不可同化道路时，图就不再是平面图了，所以说ω＝4的图着色时的色数一定是恒等于4 的。
通过以上证明，可见平面图的色数都是不会大于4的。这也就证明了四色猜测是正确的。

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

注：此文已于二○一五年四月二十八日在《中国博士网》上发表赤，网址是：

雷明85639720

,,,,,,,,