用不可避免构形法研究极大平面图的4—着色方法

雷明85639720

用不可避免构形法研究极大平面图的4—着色方法
雷  明
（二○二二年二月二十日）

1、在对一个具体的极大平面图着色时，一定是会遇对到最后一个顶点要进行着色的，当与该顶点相邻的顶点数小于4，或与该顶点相邻的顶点所占用的颜色数也小于4时，这个顶点一定可以直接着上四种颜色之一。现在要研究的是这个最后顶点的相邻顶点数大于等于4，或这个顶点的相邻顶点所占用的颜色数等于4时，如何着色的问题。
2、因为平面图中总存在着至少一个顶点的度是小于等于5的，所以在着色时总可以把最后一个要着色的顶点放在度是小于等于5 的顶点之上。所以说度是小于等于5的构形，就是平面图的不可避免构形。坎泊已经解决了度是小于等于4的构形的可4—着色问题，并且也解决了度是5的构形中的K—构形的可4—着色问题。唯独把度是5的H—构形的4—着色问题遗漏了，还没有解决。也就是说，对H—构形还没有找到4—着色的方法。K—构形是可以直接从围栏顶点中空出颜色来给待着色顶点着上的构形；而H—构形则是不能直接从围栏顶点中空出颜色来给待着色顶点着上的构形。在这篇文章中，只要把H—构形的着色方法总结出来，也就是从着色的实践中对四色猜测进行了证明。
3、构成H—构形的必要条件是图中含不含有双环交叉链，也就是说，没有双环交叉链不能构成H—构形，但有了双环交叉链却不一定就是H—构形。在BAB型的5—轮构形中，不管A—C链和A—D链交叉不交叉，都不可能空出A、B、C三色之一来。但在A—C链和A—D链相交叉的情况下，也有可以连续的移去两个同色B的构形，是属于K—构形；而不可以连续的移去两个同色B的构形，才是属于H—构形。H—构形只所以不能连续的移去两个同色B，是因为当移去了任何一个B后，都会新生成从另一个B到其对角顶点的连通链，不可能再连续的移去第二个同色B。
4、解决H—构形的4—着色问题，首先要解决的问题是把双环交叉链断开，破坏构成H—构形的条件，使构形先转化成可约的K—构形。要断开双环交叉链，首先考虑的应是改变双环交叉链的共同起始顶点A或交叉顶点A（若是多顶点交叉，只改变一个就可以了），以及两链的末端顶点C和D的颜色。这是四个关键的顶点。要改变这四个关链顶点之一的颜色，就必须交换A—B链和C—D链。为了防止交换时把图中的所有着有A、B（或C、D）二色的顶点的颜色全部都改变一次，进行无用的交换，构形中就必须要有环形的C—D（或A—B）链把A—B（或C—D）链分隔成互不连通的两部分。
5、A、B、C、D四种颜色，可能构成的链有A—B、A—C、A—D、B—C、B—D、C—D六种。现在已有A—C和A—D两种不能交换，B—C和B—D又不能连续的交换，也相当于不能交换。可交换的就只有A—B和C—D两种了。这两种正好又是一对相反链，只要有一种是环形的，就一定可以把另一种分隔成互不连通的两部分。
6、这样，H—构形就可以分为两种类型，有经过了围栏顶点的环形链的构形和无经过围栏顶点的环形链的构形。其中有环形链的构形又可分为有A—B环形链的构形和有C—D环形链的构形两种。现在就用直接构图法构造这样的几种构形如图1，图2，图3和图4。


从图中可以看出，H—构形的特征是在5—轮构形中：有两条连通链A—C和A—D，两链有一个共同的起始顶点A，中途还有交叉顶点A。有了连通的A—C链和A—D链，两链的相反链B—D链和B—C链分别都不可能再连通了。
这几个图都不可能同时移去两同色B，因为在从任何一个同色顶点B交换B—D（或B—C）时，都会产生从另一个B色顶点到其对角顶点的连通的B—C（或B—D）链，只能移去一个B，而不可能移去两个B。这也是H—构形的特征。
从图中还可以看出，最上的两个着C和D的两个顶点之间如果还有别的顶点时，图就不再是H—构形而是K—构形了。因为这时再从任何一个B色顶点交换B—D（或B—C）时，都不会产生从另一个B色顶点到其对角顶点的连通的B—C（或B—D）链，同时移去两个B则是完全可以的。这两个顶点间是一条单边也是H—构形的一个特征。应该说这两个顶点也是一对关键的顶点。
由于图3和图4两图都是无环形链的构形，只是左右不同而已，应是同一种类型，所以H—构形实际上只有如图1、图2和图3的三种类型。
7、具体极大平面图H—构形的着色方法：
对于图1的有环形链A—B的构形，交换A—B环内、外的任一条C—D链，双环交叉链就没有了末端顶点或从中间（最上的两个顶点C和D）断开，双环交叉链也就不存在了，H—构形就转化成了可约的K—构形（埃雷拉的E—图就是这样解决的）；对于图 2的有环形链C—D的构形，交换C—D环内、外的任一条A—B链，双环交叉链就没有了共同的起始顶点或交叉顶点，双环交叉链也就不存在了，H—构形就转化成了可约的K—构形（赫渥特的H—图就是这样解决的）。这两种方法都是把双环交叉链断开了，所以就叫做“断链法”。对于图3（或图4）的无任何环形链的构形，A—B链和C—D链都不能交换，那就只有先移去一个B,使图（构形）进行转型，改变构形峰点的位置和颜色，改变双环交叉链的共同起始顶点，以形成新的双环交叉链，再用以上的办法使新的双环交叉链断开。否则，若仍不能断开时，就再继续进行同方向的再转型，一定可以在有限的5次转型之内解决问题。
8、无环形链的H—构形的转型次数一定是要有上限值的。从埃雷拉的E—图的转型看，是一个无穷周期循环转型的构型，永远也不可能通过转型从轮沿顶点中空出颜色来给待着色顶点着上。那么无环型链的H—构形转型时会不会也出现这种现象呢？必须进行证明。其转型次数不但应是有限的，而且还应有一个具体的上限值。否则，有限还等同于无限。
9、由于有E—图构形的存在，它是一个无穷周期循环转型的构形。从而得到了每次转形（包括原构形在内）都是可以改变有关关键顶点的颜色而可约的构形。E—图就有这种性质。根据原命题的逆否命题与原命题有“同真同假”的逻辑关系，则有“每步转型（也包括原构形在内）都是不可以改变有关关键顶点的颜色而可约的构形，一定不是无穷周期循环转型的构形。即一定是一个有限次转型的构形”的结论是成立的。那么“有限次转型”的“上限值”是多少呢？
因为5—轮构形，有5个轮沿顶点，每个轮沿顶点都作一次峰点时，就是五次转型。转型次数大于五次时，显然就会出现循环现象。所以最大在五次转型后就应该是只有一条连通链的可约的K—构形了。而在最后一次转型的前一次转型后，得到的就一定是一个可以连续的移去两个同色的可约的K—构形了。这就证明了最大转型次数的上限值是四，或者说是五也可以。
10、上面的证明，也是一个理论上的证明。在实际中是不是这样呢？还是需要进行检验的。对图3的构形进行转型，当在移去了一个同色后，不生成从另一个同色顶点到其对角顶点的连通链时，就人为的构造连通链，使图又成为一个含有双环交叉链的H—构形，继续的进行转型，当图转化成K—构形（即不能再人为的构造连通链）时为止，转型的次数是多少，就是最大的转型次数。
对图3的构形逆时针方向转型如图5和图6。


一次转型生成了从另一个同色顶点B到其对角顶点C的连通链B—C（如图5中的加粗边），图仍是一个H—构形；二次转型生不成从另一个同色顶点D到其对角顶点B的连通链D—B（因为图6中有一条经过了围栏顶点中两个同色A的连通链A—C隔离着）。这时，图已经转化成了一个可约的K—构形。再经过一次交换后，给待着色顶点V分别可以着上D或B（如图7和图8）。两次转型解决问题，没有超过五次。
对图3的构形顺时针方向转型如图9到图12。



一次转型生成了从另一个同色顶点B到其对角顶点D的连通链B—D，图仍是一个H—构形。但这时图中又生成了一条经过了围栏两个顶点的环形链A—B（如图9中的加粗虚线边），可以改用断链法，提前结束转型；
二次转型也生成了从另一个同色顶点C到其对角顶点B的连通链C—B,还是一个H—构形（如图10）;
三次转型虽然没有从另一个同色顶点A到其对角顶点C的连通链A—C，但可以人为的构造这样的连通链（如图11中的加粗边），使图仍保持在H—构形状态；
四次转型生不成从另一个同色顶点D到其对角顶点A的连通链D—A（因为图12中有一条经过了围栏顶点中两个同色B的连通链B—C隔离着）。
这时，图已经转化成了可约的K—构形。再经过一次交换后，给待着色顶点V分别可以着上D或A（如图13和图14）。四次转型解决问题，没有超过五次。

到此，各种类型的H—构形都已是可约的了，即都可以进行4—着色了。四色猜测被证明是正确的。

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

注：此文已于二○二二年二月二十五日在《中国博士网》上发表过，网址是：
http://www.chinaphd.com/cgi-bin/topic.cgi?forum=5&topic=5048

雷明85639720

，，，，，，，，