用断链的方法给待着色顶点着色

雷明85639720

用断链的方法给待着色顶点着色
雷  明
（二○一五年四月二十九日）

一个构形的待着色顶点，如果其围栏顶点占用的颜色数未达到4，该待着色顶点都是可以着上四种颜色之一的；如果围栏顶点已占用完了四种颜色，则必须想办法从围栏顶点中空出一种颜色来，然后给待着色顶点着上。如何空出颜色，这就得要用坎泊的颜色交换技术了。
用坎泊的颜色交换技术空出颜色的原则是：对于以待着色顶点为中心顶点的轮的对角顶点的颜色所构成的链是不连通的时，才可进行交换，也才能空出颜色。而若是连通链时，即就是交换了也是空不出颜色来的。
4—轮构形一定是可以通过交换空出颜色给待着色顶点着上的。而5—轮构形其中的两条连通链只有一个共同的起点或是只有一个交叉顶点时，也一定是可以通过交换空出颜色来的，而只有两条连通链既有共同的起点，又有一个交叉顶点时，如赫渥特图，米勒图，张氏Z—构形图和L—构形图，如论无何是不能通过交换对角链的办法空出颜色的。怎么办，就得想办法对图中已有的连通链进行“断链”，使原来连通的链变成不连通的，然后再使用坎泊的颜色交换技术空出颜色来给待着色顶点着上。而“断链”的过程仍然是施行坎泊的颜色交换技术的过程，只是这一过程的交换与5—轮的轮沿顶点是无关的。我们对赫渥特图，米勒图，张氏Z—构形图和L—构形图的着色都是用的这种办法。
断链方法的原理是：用四种颜色A、B、C、D所能构成的链有六种，即A—B、A—C，A—D，B—C，B—D和C—D六种，如果有A—B链是连通的时，则该链中的A和B在该链以外，只能与C和D相邻，构成A—C链和A—D链或者B—C链和B—D链，从A—B链上的任何一个A或B顶点开始交换上述的A—C链和A—D链或者B—C链和B—D链中的一种，都可以使A—B链上的被交换的顶点A或顶点B变成C或D，使A—B链断开。这样就可以对5—轮轮沿中的顶点A或B施行A—B链的交换，空出A或B来给待着色的5—轮中心顶点着上。
可以说任何平面图中的任何链都是可以通过这一方法“断开”的，所以也就可以说明任何平面图着色时是不会用到第五种颜色的。这也就证明了四色猜测是正确的。

雷  明
二○一五年四月二十九日于长安

雷明85639720

,,,,,,,,