作一个图比原图的色数大1的方法

雷明85639720

作一个图比原图的色数大1的方法
雷  明
（二○一七年二月二十八日）

作一个图，使其色数比原图的色数大1的方法有两种。这两种方法，实际上我们在以前的文章中都已以用过了。一个是米歇尔斯基操作法，另一个就是不可同化道路法。只是我们没有象今天这样明确的这样提出过。
1、米歇尔斯基操作法：是在有v个顶点的、色数是k的图外，作一个有v个星点顶点的v—星（注意，星的总顶点数是v＋1）。然后再把v—星中的星点顶点vi（1≤i≤v）和原图中与其相对应的顶点vi的所有相邻顶点都用边连接起来（注意，v—星的中心顶点v0是与原图中的任何顶点都不相邻的），这时所得到的图的色数就比原图的色数大1，且图中的最大团不变。最大团保持不变，是因为每个星点顶点都只和原图中与其对应的顶点的相邻顶点相邻，而与这个对应顶点并不相邻。只所以所得图的色数一定比原图的色数大1，是因为v—星中的v个星点顶点均是不相邻的，他们可以同化（凝结）成一个顶点，这时，该顶点又与原图中的所有顶点都相邻了，这个顶点只能着原图中所用颜色以外的另一种颜色（因为v—星的中心顶点与原图中的任何顶点都不相邻，所以给其着上原图中的任何一种颜色都是可以的）；另一个原因是，因为v—星的各星点顶点和原图中与其相对应的顶点不相邻，均可着以和原图中与其相对应的顶点相同的颜色，这样v—星的星点顶点就占用完了原图中的所有颜色，剩下的v—星的中心顶点v0因与星点顶点均要邻，只能着以原图中所用颜色以外的另一种颜色了。
2、不可同化道路法：这里的“同化”即图论中的“收缩”，且只是指不相邻顶点间的收缩。“不可同化道路”是指图的某最大团外的一条道路，该道路总有一个顶点同化不到最大团中去。
若在一个最大团KN外有一条道路，这条道路的所有顶点都与最大团中的同一个KN－2团的各顶点均相邻，同时道路的两个端点顶点又分别与最大团中另一个K2团中有一个顶点相邻。这样，道路中除了两个端点顶点只能向那个K2团的某一个顶点同化外，道路中的其他顶点均是可向这个K2团中的任一个顶点同化。
当道路的两个端点顶点分别与K2团中的一个顶点相邻时，同时道路又是寄数顶点时，道路中总是有一个顶点同化不到最大团中去：而当道路的两个端点顶点与K2团中的同一个顶点相邻时，同时道路又是偶数顶点时，道路中也总是有一个顶点是同化不到最大团中去的。
道路有一个顶点同化不到最大团中去，就意味着最大团的顶点数增大了1。最大团是一个完全图，完全图的色数就等于其顶点数，所以最大团的顶点数的增大，也就意味着最大团的色数的增大。
3、色数变大了的图，但只要图的最大团不变成K5而成为非平面图，且其色数又不会大于4，也就能说明四色猜测是正确的（见另文）。
雷  明
二○一七年二月二十八日于金堆城
注：此文已于二○一七年二月二十八日在《中国博士网》上发表过，网址是：

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

谢谢你的支持。

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，，

雷明85639720

，，，，