平面图的着色方法

雷  明

（二○一四年七月十六日）

1、两种颜色交替着色的原则

网友国强在对我的《四色猜测的最简证明方法（修改稿）》一文的评论中说我没有自已的着色方法。我现在告诉你我着色的方法，很简单，只要是有头脑的人，都会去这么做的，不知道你能不能想到这里。

着色时，一定是会一个顶点，一个顶点的“挨个”去着色，决没有人在着了几个顶点后，又空几个顶点，又去给别的顶点着色。这样“挨个”的着色，可以做到，在一条道路上，最多只用两种颜色，在一个圈上最多只可能用到三种颜色。不在万不得已时，决不增加颜色数量，以达到用色最少的目的。这一着色方法就是只用两种颜色的“交替着色的原则”，也就是用色最少的原则。当一个度不大于5的顶点的所有邻接顶点都已着了颜色，且已用完了四种颜色时，给这一点着色时就得用坎泊创造的颜色交换技术，从该顶点的邻接顶点中空出一种颜色来给其着上。这就是当年坎泊对四色猜测的证明，可惜的是他没有考虑到所有的情况，而让赫渥特用他所构造的图把坎泊的证明给否定了。

2、破圈着色法

在坎泊的颜色交换技术的基础上，我还创造了“破圈着色法”和“断链着色法”。

所谓的“破圈着色法”就是把与未着色顶点相邻的顶点中使用次数最少的颜色给未着色顶点着上，便产生新的待着色顶点，再把新的待着色顶点的邻接顶点中使用次数最少的颜色给新的待着色顶点着上，便又产生更新的待着色顶点，这样不断的进行下去，总能找到新的待着色顶点的邻接顶点数是小于等于5的新待着色顶点，这是因为平面图中一定会存在着度小于等于5 的顶点，这个时候，再用坎泊的颜色交换技术就可以给其着色了。

坎泊在证明猜测时，是因为任何平面图中一定会存在着度小于等于5的顶点，所以他只证明到待着色顶点的度是5的情况就可以了。但是，在对具体图进行着色时，遇到的待着色顶点的度就不一定都是小于等于5的，可能会比5要大，这时对该顶点着色用破圈法较为合适。所以说破圈法适用的条件是待着色顶点的度是大于5 的情况。

3、断链着色法

所谓的“断链着色法”则是在对赫渥特图和米勒图着色的基础上总结出来的着色方法，由于待着色顶点与5个顶点相邻时，其对角顶点的颜色所组成的色链可能是连通的，即该链与待着色顶点构成了一个圈，交换这样的链是空不出颜色的，必须将该链变成不连通的，然后再使用坎泊的颜色交换技术对“断链”后的一支进行交换，就可空出颜色给待着色顶点着上。

对于只有一条连通链，或者有两条连通链但两链只有一个相交顶点时，用坎泊创造的颜色交换技术都是可以空出颜色给待着色顶点着上的。但图中含有两条连通链a—c和a—d且有两个相交顶点，并且图中含有c—d环形链时，这种图是不能直接通过坎泊的颜色交换技术空出颜色给待着色顶点的，必须进行断链，把两条连通链均变成不连通的。

断链的方法有两种，一种是从两链的相交顶点进行断链；另一种是从两链的非相交顶点进行断链。

㈠ 使用从两链的相交顶点进行断链的条件是图必须是赫渥特图型的图，即图中待着色顶点的度是5，并含有连通且相交两次的a—c和a—d链，但不含有a—b环链，而含有c—d环链，这种图的断链是从两条连通且相交的链的相交顶点进行断链，使得连通的a—c和a—d链均变成不连通链，使图变成一个含有两条连通链但只有一个相交顶点（该顶点是两链的中间顶点，使两链成为具有“×”型的交叉状）的图，然后再用坎泊有颜色交换技术对待着色顶点着色。赫渥特图的4—着色就是用的这种方法。

㈡ 使用从两链的非相交顶点进行断链的条件的图必须是米勒图型的图，这种图也具有赫渥特图的特征，但图中又同时含有环形的a—b链，与环形的c—d链相互嵌套。这种图的断链则是要从两条连通且相交的链的非相叉顶点进行断链，也可以使得连通的a—c和a—d链均变成不连通链，使图变成一个含有两条连通链但只有一个相交顶点（该顶点是两链的一个共同的起始顶点，使两链成为具有“∧”型的人字相交状）的图，然后再用坎泊有颜色交换技术对待着色顶点着色。米勒图的4—着色就是用的这种方法。

    4、“破圈法”“断链法”与坎泊的颜色交换技术的关系

所谓的破圈与断链，实际上还是在进行着坎泊创造的颜色交换技术，只不过是把这一交换技术用活了，并不只是为了空出颜色而进行交换的。破圈和断链的目的都是为了下一步在使用坎泊的颜色交换技术时能够空出颜色而进行的必不可少的颜色交换。的确有些图，首先不进行破圈或断链，的确还是不能直接空出颜色来的。赫渥特图和米勒图就是很好的例子。

破圈实际上每破一次圈，就是进行一次圈中使用次数最少的颜色与下一次破圈时圈中使用次数最少的颜色组成的链的颜色交换，直到新的待着色顶点的度小于等于5为止；而断链则是从断链的起始顶点开始，进行该顶点的颜色与所要断的链所没有的颜色组成的链的交换；两种交换的结果，都使得连通链开始断链的顶点的颜色改换成了非该链的颜色，达到了使连通链断开的目的；这实质上还都是在进行着坎泊的颜色交换技术，只不过交换的目的不同罢了。

雷  明

二○一四年七月十六日于长安

注：此文已于二○一四年七月十六日在《中国博士网》上发表过，网址是：

http://www.chinaphd.com/cgi-bin/topic.cgi?forum=5&topic=2196&show=0