[讨论]评刘福的《改进坎泊的调色法》

雷明85639720

刘福前几天（3月4日）发表了《改进坎泊的调色法》一文后；我3月5 日发表了评论：“朋友，你这个“改进”实际上是错的。你在b—g链上的某条边中增加一个顶点，着r色，然后把顶点2 的b改着成了g色，似乎是空出了b色，但你的前提是“在b—g链上的某条边中增加一个顶点”，并着r色，你没有想一想，你这个“着r色的顶点”如同几何证明中所作的辅助线一样，它并不是原图中的顶点，还是要去掉的。如果去掉了该顶点后，不就又产生了两个相邻顶点同着上了g色吗，不等于还没有完成着色任务吗。你可以按你的方法，在你所引用的赫渥特图上去作一作。雷明，2012,3,5,”刘福3月5日当日回复说：“后加的那个点及所着的颜色就不去掉了！这就是改进的所在。因为这样做并没有减少图的着色数。”我说，你这话说得非常的错误。我问你，你是在给H—图着色呢，还是在给你给Heawood—图增加了那个顶点后的非Heawood—图在着色呢，那还能叫Heawood—图吗，那样的着色谁不能做到呢。你这算什么改进嘛。雷明，2012,3,7,

LIUFU

【改进肯泊的调色法】目的是在给出一个证明：如果一个顶点v与五个其它用四种颜色着色的点邻接，那么总能多出诸颜色之一用来给v着色(摘自【图论的例和反例】p10）.图中数字1、2、3、4、5表示五个邻接点，它们之间的短线代表两点相邻；括号内的字母r 、b 、y、 g分别代表红、蓝、黄、绿四色。
   在证明中，我用到的图形就是发到贵栏目的那个图；因为我要举例子，用的是在新浪网平常心博客中带有序号的希伍德反例图，非常便于交流！可惜，没有发上来。   
    我在原文证明中，对不失一般性的图形来说，确实使用了增加点的办法，按雷明的理解就像作辅助线一样，本人不反对；以后在与他的交流中没有使用增加点（虽然可以），而是用图中原来的点，调色链是：2(b)-->9(r)-->16(g)-->25(r)-->19(g)-->7(b)-->1(r).
   本人愿意洗耳恭听。

LIUFU

首先，我表示非常愿意接受您的质疑。我的加点调色在原图中增加一个点，即表示否定了原图，它就像您的蓝红链破坏交叉链那样；由于我的这一做法并不减少图的着色数，所以还是可以用的。您说的很形象，就当是做了辅助线（这里是点）。这也是本人受您“一个点是一个特殊的链”的思想的影响。这也是我说过的您的先破链再交换的“他山之石”之价值！您的那“石”只能对付反例图的交叉链，我拿来对付更一般的“五邻点四着色”。由于我站得不够高，就看到这一点儿；得先感谢您---连续发表之42！
  上面给您的那个调色连还不是我用来作证明用的加点调色法，只是让您体会它有多么麻烦---想变就变，无定法，别人看不懂，只有我自己能看懂。同时这也间接说明了由于方法不同，是可以避免产生通到v的链，使点1由r改为g的。
  真正用到“加点调色”，您一试就感觉出来它的作用了。那是谁都能做到的事！

雷明85639720

我破坏两交叉键，只是改变了交叉点的颜色，关没有增加或减少图中的顶点，图的本来面目并没有改变。

刘福

我先搬来个图
............2(b)--
.........../....\
........../......\
.........1(r)....3(r)
.........|....v...|
.........5(y)----4(g)--
.........|
我方法重要一点，利用原图一对同色顶点（1、3），它的潜在价值以后再谈。不论多么复杂的图只调一个顶点，如2（g),将b移到以2为顶点的边上！
空出的b色给v .
     我的方法，不需破链。
  全过程只动两点！0k.

雷明85639720

你认为你只动两个点也有可能，但你对赫渥特图调一下色看看，你算一算你一共动了多少个顶点的颜色。自已动手调一下吧。

刘福

给任何图作调色，都不超过两个点；以前给您举的例子，我是用了反例图。为了让您看懂，特意指出当链长大于1时，可以用图中的点来替代（也让使用者感到图本身没有变化）“加点”。但调色法的本意确实不需要这一系列的顶点！

雷明85639720

你认为你只动两个点也有可能，但你对赫渥特图调一下色看看，你算一算你一共动了多少个顶点的颜色。自已动手调一下吧。雷明