Mycielski—操作与四色猜测

雷明85639720

Mycielski—操作与四色猜测
雷  明
（二○一四年三月二十三日）
（图请见上面的DOC文件）
1、Mycielski—操作
数学家狄拉克1953年在其论文《k—色图的构造》一文中提出一个问题：对于任意大的一个正整数k，是否存在一个图，不包含三角形但色数是k？这一问题分别在1954年和1955年分别由勃兰克•斯德卡兹和米歇尔斯基独立的作出了回答。
米歇尔斯基（Mycielski）给出的由一个不含三角形的k色图Gk构造一个不含三角形的k＋1色图Gk＋1的方法是：设Gk的顶点是u1, u2,……，un, 添加点v1,v2,……，vn和点v0。将vi与ui所有邻点及v0相连，1≤i≤n。如此得到的图就是一个不含三角形的k＋1色图。
米歇尔斯基（Mycielski）给出的这一过程数学界称之为Mycielski—操作，简称M—操作。这里所说的“不含三角形”的图实际上就是密度不大于2的图，因为这种图中不含有K3团，当然就是“不含三角形”的图了。
“图的密度”是聂祖安所译《图论的例和反例》中的术语，也就是图论中的的“团数”。因为“团数”的概念不清，是指团的数量呢，还是团中的顶点数呢，没有说清楚；另外，图中有顶点数不同的各种团，“团数”是指那种团所言的呢，也不明确，所以我不用“团数”，而用“图的密度”的术语。
一个5—圈（色数是3）经过M—操作后所得到的结果是一个色数为4的图，如图1。可以看出，5—圈的5个顶点ui（用带圈的数字标注）以外所添加的5 个顶点vi（用不带圈的数字标注）和一个v0构成的是一个以v0为中心的5—星图，5 个vi星点顶点均是不相邻的，每一个星点顶点vi与5—圈中的两个不相邻的顶点ui－1和ui＋1是相邻的，而不同时与5—轮中相邻的两个顶点相邻。这样做，就既可以保证图的密度不会变大而仍然是2（即图中无三角形），又可以保证图的色数可增加1的目的。

由于5个星点vi是互不相邻的，所以可以凝结为一个顶点（即可着同一颜色，图1中为黑色），这时该顶点就与5—圈中的5个顶点构成了一个5—轮，是一个奇轮，一定是要用四种颜色着色的，且无论n是奇数还是偶数时，n—轮的色数一定是比n—圈的色数大1 的，这是因为轮的中心顶点绝对不能与轮沿顶点是相同颜色的，这些轮沿顶点就是构成轮的那个圈中的所有顶点。同时我们一定要注意到图1是一个非平面图。
厦门大学的图论博士杨卫华老师说：“重复进行Mycielski操作，每操作一次色数都增加1，且团数不变（每一次都是保持无导出三角形，故团数不变）。比如以5—圈出发，用一次Mycielski操作色数变为4，对得到的图再进行一次Mycielski操作色数就变成了5，以此类推会出现6色无三角形图，7色无三角形图，8色，9色……”。杨老师指出“Mycielski构造的图说明：存在无三角形且色数任意大的图”。他还继续说“M—操作可以以任何图为基图，而不是仅仅以圈为基图，M—操作的的结果就是使得所得图比基图色数增加1。”这就是说进行M—操作的基图的密度不一定都是2，密度大于2 的图也是可以进行M—操作的。
2、Mycielski—操作与四色猜测
既然“Mycielski构造的图说明：存在无三角形且色数任意大的图”，且“Mycielski—操作可以以任何图为基图”。那么，如果平面图进行了M—操作后，所得到的图只要不是非平面图，其色数也都不大于4时，四色猜测就是正确的，否则猜测就是错误的。当然了，如果平面图进行了M—操作后，所得到的图成为非平面图时，它就不再是四色猜测研究的对象了，因为猜测所研究的图是平面图。
如果一个平面图的色数是γ,要保持其密度ω不变，而色数又要增加1时，只要对图中某最大团Kω（该团的顶点数ω就是图的密度）进行一次M—操作就可以了。要使该团的顶点数即密度ω不增大，所添加的n（n＝ω）个星点顶点vi（1≤i≤n）中的任何一个顶点与该最大团Kω中的ω个顶点最多只能有ω－1个相邻，才能保证图的密度不变。
当任一个星点顶点vi（1≤i≤n）都与最大团Kω中各不相同的ω－1个顶点相邻时，这n（n＝ω）个星点顶点（1≤i≤n）就已占用完了图中所用的γ（γ＝ω）种颜色，星形图的中心顶点就只能用γ种颜色以外的颜色了，图的色数变成了γ＝ω＋1。
顶点数为ω的团Kω中有ω个顶点，在进行了M—操作时，共增添n＋1个顶点，由于n＝ω，所以进行了M—操作后的图中共有ω＋n＋1＝ω＋ω＋1＝2ω＋1个顶点；最大团Kω中有ω（ω－1）/2条边，进行了M—操作时，共增添n（ω－1）＋n条边，也是由于n＝ω，所以进行了M—操作后的图中共增添了ω（ω－1）＋ω条边，这时图中共有ω（ω－1）/2＋ω（ω－1）＋ω＝（ω2－ω）/2＋ω2条边。
3、四色猜测的证明
现在我们从密度的角度来一个个的证明密度不大于4的平面图的色数都是不会大于4的：
① 密度是1和4的平面图的色数一定是小于等于4的：
平面图有边数小于等于3倍的顶点数减6的关系。若有（ω2－ω）/2＋ω2＞3（2ω＋1）－6＝6ω－3时，这时的密度为ω的图就不能进行M—操作，因为进行了一次M—操作后，图就成了非平面图。用这个关系可以对所作的图进行校核。
平面图中基本的团是K1，K2，K3和K4，即平面图的密度只有ω＝1，ω＝2，ω＝3和ω＝4四种，首先对这四种团分别进行M—操作，如图2～图5。这四种团的色数分别是1，2，3和4，进行了一次M—操作后的图的色数分别是2，3，4和5。
因为M—操作中所添加的ω个顶点vi和v0是构成了一个星形图，而星形图本身的密度就是2，而K1本身的密度却是1，所以密度是1的图进行了M—操作后，是不能保证图的密度不变的。图2的虽然色数是2，比K1的色数1增大了1，但其密度也变成2了，而不再是K1的密度1了。所以说密度ω＝1的图是不能进行M—操作的。也就是说密度ω＝1的图的色数一定是等于1 的，是不大于4的。

图5也是一个色数为5的非平面图，说明K4在了进行M—操作后虽然色数增大了1，但却不再是平面图了，这已不再在四色问题研究的范围之内了。所以说K4的色数也是不会大于4的。
以上就证明了密度ω为1和4的平面图的色数一定是小于等于4 的。
现在对图2到图5的平面性进行检验如下：
尽管图2中不ω＝1的图是不能进行M—操作的，但其（ω2－ω）/2＋ω2＝1（与图中相符）＜6ω－3＝3,所以图2仍是平面图。图3中ω＝2，（ω2－ω）/2＋ω2＝5（与图中相符）＜6ω－3＝9，图4中ω＝3，（ω2－ω）/2＋ω2＝12（与图中相符）＜6ω－3＝15，所以这两个图也都是平面图。而图5中ω＝4，（ω2－ω）/2＋ω2＝22（与图中相符）＞6ω－3＝21，所以图5不是平面图。
② 密度是2和3的平面图的色数也是小于等于4的：
以上①的证明不仅说明了密度为ω＝1和ω＝4的平面图的色数是不大于4外，还说明了密度为ω＝2 和ω＝3的平面图在进行了一次M—操作后仍是平面图。这就说明密度为ω＝2和ω＝3的平面图的色数就可以比其密度大1了，其色数分别可以是3和4，如图3和图4。现在再看密度为ω＝2和ω＝3的平面图是否还可再进行第二次M—操作了。如果都是否定的，则就说明了密度为ω＝2和ω＝3的平面图的色数也是不大于4 的。
密度为ω＝2的平面图，有两种情况，一是含圈，一是不含圈。不含圈时，对任何一个K2团进行M—操作后都会得到图3的5—圈，其色数是3。若对这个5—圈再进行一次M—操作后，得到的将是一个与图1相同的色数为4的非平面图，这不符合要求。密度为ω＝2且含圈的图，图中最小的圈应是4—圈，因为含3—圈的图的密度就不是ω＝2， 而是ω＝3了。若对4—圈再进行一次M—操作（如图6），得到的却是一个非平面图，也不符舍要求。这就证明了密度是2的平面图的色数也是不会大于4 的。

密度为ω＝3的平面图，在对其中的任何一个K3团进行了M—操作后，都得到的是如图4的图。这个图4中有3—圈，也有4—圈。对3—圈进行M—操作，得到的还将是与图4相同的图；对4—圈进行M—操作，得到的则是如图6的非平面图，也不符合要求。这就证明了密度为ω＝3的平面图的色数也是不会大于4 的。
这也就证明了密度是2和3的平面图的色数也是小于等于4的。
4、结论：到此就证明了任何平面图的色数都是小于等于4的，四色猜测是正确的。
雷  明
二○一四年三月二十三日于长安

任在深

      
              □□□□□□□□□
              ■■■○○○◇◇◇
              ○○○◇◇◇■■■
              ◇◇◇■■■○○○
              □□□□○○◇◇◇
              ■■■◇◇◇○○○
              □□□□□□□□□