平面图4—着色的步骤（修改稿）

雷明85639720

平面图4—着色的步骤（修改稿）
雷  明
（二○二二年九月六日）

1、备用A、B、C、D四种颜色。选任一个顶点做为起着点，用轮形图着色法，先用一种颜色着轮形图的中心顶点（起着点），再用另外两种颜色交替的依次对轮形图的轮沿顶点进行着色，两种颜色不够用时再用第四种颜色。轮形图是偶轮时，总共用三种颜色就够了；奇轮时，总共用四种颜色也就够用了色。
2、以已经着色的一个顶点作新的轮的中心顶点，对其未着色的轮沿顶点再进行着色。
3、对以上1、2两步反复的进行操作。
4、当遇到与要着色的顶点（待着色顶点）相邻的顶点（围栏顶点）已占用完了四种颜色时，这就是一个平面图的“构形”。
5、先看待着色顶点的度是否大于等于6？
5、1  若是。这是一个可以避免的平面图构形。选围栏顶点中使用次数最少的一种颜色，将其着在待着色顶点上，使待着色顶点进行移动。并且使图中产生大于等于1个的新待着色顶点。再反回到第5步。
5、2  若不是。
6、再看围栏顶点所占用的颜色数是否小于等于3？
6、1  若是。这就是可以给待着色顶点直接着色的构形。备用颜色中至少还有一种颜色可以给待着色顶点着上。着色后再返回第2步。
6、2  若不是。
7、再看待着色顶点的度是否等于4？
7、1  若是。这就是一个度是4的4—星构形（即4—轮构形），根据1879年坎泊的证明，4—星构形一定是可约的。
7、2  若不是。那就一定是一个5—星构形了。以一个BAB型的5—星构形为例，其围栏顶点的峰点顶点一定是着A色，两个同色顶点一定是着B色。
8、还可看，是否可以通过简单的一、两次坎泊的可以空出颜色的颜色交换技术，直接从围栏顶点中空一种颜色给待着色顶点着上？
8、1  若可以。这就是坎泊在1879年已经证明过的是可约的K—构形。其待着色顶点一定是可以着上图中已用过的四种颜色之一的。着色后再返回第2步。
8、2  若不可以。则一定是赫渥特1890年给出的含有双环交叉链A—C和A—D的H—构形。这种构形是不能直接从围栏顶点中空出任何一种颜色给待着色顶点的。
9、再看图中有没有经过了围栏顶点的环形的A—B链或C—D链？并能把与环形链A—B呈相反链的C—D链中的属于双环交叉链A—C和A—D的两个末端顶点（关键顶点）C和D构成的C—D链与其他的C—D链分隔成位于A—B环内、环外互不连通的两部分；或能把与环形链C—D呈相反链的A—B链中的两个关键顶点——双环交叉链A—C和A—D的共同起始顶点A和至少一个交叉顶点A分隔在C—D环的两侧？
9、1  若有环形链。用断链法使构形直接转化成可约的K—构形。
9、1、1  若有A—B环形链。交换A—B环形链内、外的任一条C—D链都可使双环交叉的A—C链和A—D链断开，构形成为可以从围栏顶点中空出任何一种颜色给待着色顶点的可约的K—构形。着色后再返回第2步。
9、1、2  若有C—D环形链。交换C—D环形链内、外的任一条A—B链都可使图中不再含有双环交叉的A—C链和A—D链，而构形由BAB型转化成了ABA型的构形。图中虽然仍含有两条连通的B—C链和B—D链，但却不“十字”相交叉，是一个可约的K—构形，是可以从围栏顶点中空出两个同色A的可约的K—构形。着色后再返回第2步。
9、2  若没有环形链。解法见第9步。
10、没有环形链的H—构形的可约方法：
10、1  利用无环型链的H—构形与有环型链的H—构形可以相互转化的特性，直接把无环形链的H—构形转化成有环形链的H—构形的方法。用断链法进行解决。着色后再返回第2步。
10、2  转型交换法。最多只需40次同方向的连续转型，一定可以给待着色顶点着上图中已用过的四种颜色之一。是一个可约的形。在转型的过程中，还有可能转化成有环形链的H—构形，再用断链法进行解决，以提前结束转型。着色后再返回第2步。
10、3  局部断链法。有时在双环交叉链上，局部地方还有环形链，可在局部环形链内进行相反色链的交换，使一条连通链A—C或A—D断开（局部断链），使构形转化成只有一条连通链的可约的K—构形。着色后再返回第2步。
11、直到把图中所有的顶点着色完毕为止。每一个步骤都有两种相反的可能，一种是可以解决问题的情况，另一种是暂时看来还是不可以解决问题的情况。但这种暂时看来还是不可以解决问题的情况，在下一个步骤中又有两种情况，一种是可以解决问题的情况，另一种仍是看来还是不可以解决问题的情况。直到第9步，第10步所得到的各种情况都是可以解决问题时为止。在整个着色的过程中，是与图中的顶点数的多少没有关系的；而只与构形的类型和围栏顶点的多少有关，以及与在围栏顶点外的连通链的类型和多少有关。可见四色猜测对于任何平面图都是适用的，也是正确的。平面图中的顶点多少也可以是无穷的。

        雷  明
二○二二年九月六日于长安

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，