平面图4—着色的步骤

雷明85639720

平面图4—着色的步骤
雷  明
（二○二二年七月十一日）

1、开始着色，剩下最后一个顶点未着色。
2、这个未着色的顶点的度是否大于5：若是，用待着色顶点移动法，把待着色顶点移动到度是小于等于5的顶点之上。
3、待着色顶点是否可直接着色：若是，问题就解决了；若不是，再进行下一步：
4、待着色顶点是否是4—度的：若是，一定是可4—着色的，问题也就解决了。若不是，则就是5—度的，进行下面的步骤：
5、看有无连通链：若无，一定可以4—着色。若有，再进行下面的步骤：
6、有一条，一定可以通过K—交换法从围栏顶点中空出一种颜色给待着色顶点的。有两条时，还要看相交不相交：若不相交，一定可以空出两个同色来的。若相交，还要进行下列的步骤：
7、看是那两条链相交：若是两条关于两个同色的链相交，是可以空出其他三色之一来的。若是两条关于峰点的颜色的链相交，再看能否连续的移去两个同色：
8、能连续的移去两个同色者，待着色顶点可以着上移去的两个同色的颜色。以上的构形均是K—构形。不能连续的移去两个同色者，就是H—构形。下面专门进行研究：
9、看图中有没有经过了围栏邻角顶点的环形链：
9、1  若有，还要看是那种链：若是关于峰点颜色和两个同色的颜色的环形链时，交换环内、外的任一条与环形链呈相反链的链，可以使构形转化成可约的K—构形；若是关于双环交叉链的两个末端顶点的颜色的环形链时，同样也是交换环内、外的任一条与环形链呈相反链的链，也可使构形转化成可约的K—构形。
9、2  若没有，就只得先交换一个关于两个同色的链，先移去一个同色，再看转型后的构形是否是可以转化成可约的K—构形。这一过程可以连续的进行，且一定会在不大于40次的转型次数之内，使构形转化成可约的K—构形的。

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，