平面图可4—着色的流程

雷明85639720

平面图可4—着色的流程
雷  明
（二○二○年二月二十一日）

平面图可4—着色时，用的是轮形图着色法。即对以已知着色顶点为中心的轮的轮沿顶点着色。当遇到待着色的顶点的相邻顶点均已着色，且占用完了四种颜色时，这就是一个轮形构形。因为任何平面图中一定存在顶点度是小于等于5的顶点，所以一定可以把构形的待着色顶点放在度小于等于5的顶点之上。而度小于等于4的待着色顶点，坎泊已经证明都是可以着上四种颜色之一的。这里就只对度等于5的待着色顶点进行讨论。
首先，判断已知构形的类型，用是否可连续的移去两个同色的办法进行判若两人断。可以连续的移去两个同色的是K—构形，把两个同色的颜色给待着色顶点着上，问题也就已经得到了解决；不可连续的移去两个同色的则是H—构形，然后
第二步，再判断图是那种类型的H—构形，用有没有经过构形围栏顶点的环形链的办法进行判断。有环形链的是“有环形链的H—构形”，用交换环形链内、外的任一条相反链的“断链交换法”的办法，使构成H—构形的必要条件——“双环交叉链”断开，构形转化成K—构形而解决；无环形链的则是“无环H—构形”，然后用转型交换的方法进行解决。在转型的过程中，若转化成了有环形链的H—构形时，则改用断链交换法解决；若转化成了可以连续的移去两个同色的构形时，问题也就可以得到解决；否则，再继续进行转型，最多不会超过40次转型，一定会转化成可以连续的移去两个同色的构形的。
把已知图中的所有顶点都用以上的着色方法着色完毕时，该图的可4—着色也就完成了。
流程图如下：

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

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

雷明85639720

，，，，，，，，