[原创]任意图顶点着色的色数函数式及四色猜测的证明（节选）.

雷明85639720

[watermark]

任意图顶点着色的色数函数式
及四色猜测的证明（节选）
雷  明
（一九九四年十二月二十日）
………………
（本次节选按：本文以上通过对图顶点的着色与同化，以及图的色数与最小完全同态的顶点数的关系的研究，得到了图的色数就等于图的最小完全同态的顶点数的关系，进而又得到了图的色数与图的密度间有）
γ（G）≥ω（G）                              （5）
的关系。这就是1970年Sachs给出的任意图顶点着色色数与图的顶点的关系。这是一个必然的结果，但它仍不能确定一个图的色数的具体值。
四、图顶点着色的色数函数式
1、色数是图的结构参数的多元函数
任何一个图的色数只可能是一个肯定的值，这是毫无凝问的，但公式（5）却确定不了这个具值。密度虽是图的一个重要结构参数，但密度相同的一类图的色数却不一定都相同，圈的密度是2，但奇圈的色数却是3，而偶圈的色数才是2，轮也有类似的情况。这就说明，色数不仅仅只取决于密度值，还可能与图的其它结构参数有关。若把其它参数统统暂用一个变量ε来表示，则色数这个多元函数可以表示为
γ（G）＝f（ω，ε）                          （6）
现在的问题就是确定这个ε是一个或多个什么样的参数了。
2、最大团个的顶点与最大团的关系
设某最大团Kω外的任一顶点与Kω团有a个顶点相邻（0≤a≤ω－1，a∈ω），由这a个顶点所构成的团用Ka表示（Ka Kω），则最大团Kω外的任何团Kn（1≤n≤ω）的各顶点所对应的且包含于最大团Kω内的n个Ka团的交集Km为
Km＝Ka1∩Ka2∩……∩Kan Kω－n                 （7）
当n＝时，由（7）式可知，最大团外的任一个K2团所对应的Km为
Km Kω－2                                      （8）
由于任何一条道路Pn都是由n个K2团构成的，所以最大团Kω外的任何一条道路Pn中的各个K2团对应的Km的交集Kp同样也应是
Kp＝Km1∩Km2∩……∩Kmn Kω－n                 （9）
这也就说明了最大团Kω外的任何一条道路Pn各顶点对应的包含于最大团Kω内的n＋1个Ka的交集Km同样也是
Km＝Ka0∩Ka1∩……∩Kan Kω－n                （10）
亦即
m＝ω－2                                    （11）
这就是说，最大团Kω外的任何道路中各顶点与最大团内相邻的顶点的交集的顶点数至少要比最大团的顶点少2 。
3、最大团外的道路向最大团的同化
（一）当Km Kω－2，即m＜ω－2时，Pn中各顶点全部可以同化到
最大团Kω中去。
（二）当Km＝Kω－2，即m＝ω－2时，有两种情况：
（1）所有的a＝ω－2或中有一个a＝ω－1，而其它的a＝ω－2时，Pn中各顶点也可全部同化到最大团Kω中去。
（2）有两个以上的a＝ω－1时，这两个顶点间就是所要研究的对象Pn。这时又有两种情况：
① Ka1∩Kan＝Kω－2，当Pn为奇长（偶数个顶点）时，Pn中各顶点全部可以同化到Kω中去；当Pn为偶长（奇数个顶点）时，总在一个顶点同化不到最大团Kω中去。
②Ka1∩Kan＝Kω－1，与上述①正好相反，Pn为偶长时，Pn中各顶点全部可以同化到Kω中去，而Pn为奇长时，也总在一个顶点同化不到最大团Kω中去。
把这种不可能把全部顶点同化到最大团Kω中去的道路叫特殊道路，用Qn表示。不难看出，当Qn是一条闭合道路（圈）时，只有Ka1∩Kan＝Kω－2一种可能，因为当Qn闭合时，Ka1∩Kan＝Kω－1时，图的密度就不再是ω，而是ω＋1了。
4、色数函数式
（一）对某一个最大团Kω而言，若存在数条Qn时，但其间均无联（联即和，两个图G1和G２的联是任一个图中的任一个顶点均与另一个图中的所有顶点全部都有边相邻，用G1＋G２代表G1和G２的联）存在，各条Qn中同化不到Kω团中去的那一个顶点因其互不相邻而全可凝结成一个顶点，实际上这数条Qn同化的结果与一条Qn的效果是相同的，即无论有多少条Qn，同化的最终结果只有一个顶点同化不到最大团Kω中去。
（二）若数条Qn中两两均有联存在，由于各条Qn中同化不到Kω团中去的数个顶点间全部均相邻而不面能再凝缩成一个顶点，所以有多少条Qn就有多少个顶点不能同化到最大团Kω中去。
（三）如果把无Qn存在的情况也视为存在，这可认为Qn是一个空集 ，其中既无边也无顶点，其条数为０。当有一条Qn时，可认为Qn与 的联仍是那条Qn，用 ＋Qn1表示，若另外还有一条Qn与原来的Qn１有联存在时，则可用 ＋Qn１＋Qn１表示，依此类推当第ε条Qn与前ε－１条Qn也有联存在时，可用 ＋Qn１＋Qn１＋………＋Qn（ε－１）＋Qnε表示。这里可把ε叫做联重数，ε≥０，当ε＝０时，就意味着无Qn存在，即Qn＝ 。若再把 用Qn０表示时，则重联式可用下式表示
Qn０＋Qn1＋Qn2＋……＋Qnε                     （12）
ε为几，重联数就是几。ε就是决定图顶点着色的另一个结构参数，其值就是最小完全同态的顶点数比最大团的顶点数多出的数值。把ε的值代入公式（4）则有，
γ（G）＝α(G)＝ω(G)＋ε(G)                 (13)
和
γ（G）＝ω(G)＋ε(G)                      （14）
这就是图顶点着色色数的二元函数式。
5、色数的界
（一）对于“图”这个集合来说，公式（14）是没有上界的，其值随密度的增大而增大。因为密度至少是1，所以对于图顶点着色而言，其色数的下界是1。
（二）对于同一密度下的一类图或一个图来说，其色数（公式（14））则是有界的，下界是ω（G），这就是ε＝0时的情况；其上界则取决于ε的最大值是多少。在重联数为ε的ε条Qn中各任意指定连续的两个顶点，则在这2ε个顶点间最大可构成一个K2ε团，由于2ε≤ω，所以ε≤ω/ 2，又因为Qn的条数必须是整数，所以还要对ω/ 2向下取整，即ε≤＜ω/ 2＞，这时就有图顶点着色色数的上界为ω(G)＋＜ω/ 2＞。
（三）综合上述，可得到密度一定的图顶点着色色数的界是
ω(G)≤γ(G)≤ω(G)＋＜ω(G)/ 2＞≤＜1.5ω(G)＞  (15)
即任何图顶点着色的色数不会小于其密度，也不会大于其密度的一倍半。
五、四色猜测的证明
1、平面图四色猜测的证明
由于平面图的密度都不大于4，所以对于ω≤3的平面图来说有：
（1）ω＝1时，ε≤＜ω/ 2＞＝＜1/ 2＞＝0,代入（14）式得γω＝1＝ω＋ε＝1＋0＝1；
（2）ω＝2时，ε≤＜ω/ 2＞≤1，ε有0和1两种可能，分别代入（14）式得γω＝2＝ω＋ε＝2＋0＝2和γω＝2＝ω＋ε＝2＋1＝3；
（3）ω＝3时，ε≤＜ω/ 2＞≤1，ε有0和1两种可能，分别代入（14）式得γω＝3＝ω＋ε＝3＋0＝3和γω＝3＝ω＋ε＝3＋1＝4；
以上三点说明ω≤3的平面图的色数都是不会大于4的。
（4）对于ω＝4的平面图，由于ε的值可能有0、1和2 三种情况（ε≤＜ω/ 2＞≤2），当ε＝0时，代入公式（14）得γω＝4＝4，当ε取1 和2时，色数γ都将大于4，但当ε≥1时，这个图就不再是平面图了，画者可自已画图试一试。可见ω＝4的平面图，其色数只可能有γω＝4＝ω一种，即γω＝4＝4。
可见，任何平面图顶点着色的色数是决不会大于4的，平面图的四色猜测就得到了证明。即有
γ平面图顶点着色≤4                                 （16）
………………
4、地图四色猜测的证明
地图本身就是一个平面图，它的对偶图仍是平面图。给地图中区划（面）的着色，就是对其对偶图的顶点着色，根据公式（14）和（16）其色数一定不会大于4，于是有
γ地图区划着色≤4                                 （17）
到此，1852年Francls提出的地图四色猜测（又一说是为1842年由Mobius提出的）就得到了证明是正确的。
5、地球地图的色数
以上所讲的地图都属于广义地图，它只有区划而不管区划的属性，它的着色实际上就是平面图的面着色，其色数就是公式（17）。
而地球地图中的区划却有其不同的属性，有陆地与水域（海洋，湖泊）之分。若要把水域与陆地区划的颜色明显区分开来，就必须人为的增加一种颜色来表示水，就时就有
γ地球地图着色≤5                                  （18）
但这却并不影响四色猜测的正确。因为如果把水（海洋）的颜色再改回至不分区划属性时所用的颜色时，地球地图的色数仍是不会大于4 的。
6、月球地图的色数
月球上只有陆地而无水，无论将其表面怎么划分区划，其色数总是有
γ月球地图着色≤4                                （19）
的关系。
………………
　　　　　　　　　　　　　　

雷  明

一九九四年十二月二十日于金堆城矿