改进肯泊的调色法

刘福

通过学习雷明连续发表之42，他的“一个顶点是一条特殊的链”的思想。本人对肯泊关于四色问题的证明有了新的改进考虑。
  思路：不在两次交换不连通的二色链！它的弊端是别人利用这些交换的点制造矛盾。而是专致于一次交换或关注连通的二色链。
证明：如果一个顶点v与五个其它用四种颜色着色的点邻接，那么总能多出诸颜色之一用来给v着色(摘自【图论的例和反例】p10）.图中数字1、2、3、4、5表示五个邻接点，它们之间的短线代表两点相邻；括号内的字母r 、b 、y、 g分别代表红、蓝、黄、绿四色。
/-----------------\
|                 |
5（y)----1(r)-----2(b)-\
|                 |    0
|       v         |    |
|                 |    |
4(g)--------------3(r) |
|                      |
\----------------------/
  肯泊关于四色问题的证明在【数学证明】一书中有介绍，我认为是诸多专著中最贴切的一种。肯泊证明的实质是调色----在用除待着色顶点以外的其他所有顶点已用过的四种颜色来调色。这种方法具有深远的的意义。为什么这么说，大家猜他怎么不用归纳法？这是受当年图论的知识的局限，还没有作为归纳法所需要的能从k传递到 (k+1)的引理（现在不一样了）！
就是在图论知识丰富的今天，我们照样可以用肯泊的调色法。特别是当他的证明遇到希伍德反例图的冲击后，他的调色方法仍可发挥作用！
  观察图中的二色链:2（b)至4（g)及2（b）至5（y)。1）如果有一条二色链是不连通的，则立即可调出一对同色；与原有的一对同色及另一单色使五邻点构成三色，可空出一色給待着色顶点。2）如果这两条中有一条是连通的，则可不必去看另一条的情况。在连通的这条链上，从某个端点起的第一条边上取（重新找）一点，着上与边的端点（如b、g）不同的第三色，然后将这个端点的颜色（如b)调为另一个端点的颜色-----重新制造出一对同色(如gg)！最后，使五邻点着三色(如r、g、y)，空出四色中的一色（如b)给待着色顶点。


解读Kempe的证明㈣：Heawood反例  (2011-05-03 10:37:01)[删除]
标签：  转载  
原文地址：解读Kempe的证明㈣：Heawood反例作者：平常心
    1890年，P.J.Heawood举出一个反例（见图4），说明Kempe证明平面图不含结构R的方法并非总是对的。





以图4（1)Heawood反例图为例，其中的2（b)至4(g)链为蓝、绿二色链，路线是：2--9--15--4；在该链上从端点2（b)起的第一条边（2--9）上取一点并着与b和g皆不同的第三色---r色，随即将端点2的b色改为g色，只有这小小改动，就达到u的五邻点有两对g两对 r及一个y色，共计三着色的调色目的。从而待着色点u可着上b色！
  读者感兴趣可接着练习：1）从以4（g）为端点的第一条边上取点做起......，最后使u着g色；2）同样道理，也可在另一二色链2（b)至5（y)做两种练习。
  另外雷明连续发表之42的第4部分“一个与五个顶点相邻的待着色顶点的着色实例”中的许多图都可作为练习用。
  
  

   

   


   

文字

雷明85639720

朋友，你这个“改进”实际上是错的。你在b—g链上的某条边中增加一个顶点，着r色，然后把顶点2 的b改着成了g色，似乎是空出了b色，但你的前提是“在b—g链上的某条边中增加一个顶点”，并着r色，你没有想一想，你这个“着r色的顶点”如同几何证明中所作的辅助线一样，它并不是原图中的顶点，还是要去掉的。如果去掉了该顶点后，不就又产生了两个相邻顶点同着上了g色吗，不等于还没有完成着色任务吗。你可以按你的方法，在你所引用的赫渥特图上去作一作。雷明，2012,3,5,

LIUFU

后加的那个点及所着的颜色就不去掉了！这就是改进的所在。因为这样做并没有减少图的着色数。

刘福

因为文章中的图被删掉，有关心的网友请到新浪网去查看。[br][br]-=-=-=-=- 以下内容由 刘福 在 时添加 -=-=-=-=-
该文是借鉴雷明对希伍德反例图的研究，他在解决两个连通的交叉链时使用了一个能够不交换到底的办法----将这个交叉点是为特殊的链，进行兰红（b、r)交换破换连通性，然后在交换----达到5邻点的四着色转变为5邻点地三着色！
  我现在利用这一思想，研究出在边上加点（也可以理解为辅助点法）并着上第三色，可直接把原来链上的端点调为一对同色。
  这样，加上原图就有的另一对同色，还有一个单色，5 邻点成为三色之目的达到。
  只动用一、二个点，非常便捷。请网友检验，并提出宝贵意见！