用交换邻角链解决H—构形的着色问题

雷明85639720

用交换邻角链解决H—构形的着色问题
雷  明
（二○一八年九月二十一日）

仍以BAB型的5—轮构形为例来说明问题。
平面图的构形总的可分为两大类，即K—构形和H—构形。而H—构形又可分为三类：一类是含有经过5—轮的1B，2A和3B三个轮沿顶点的A—B环形链的构形，一类是含有经过5—轮的4D和5C两个轮沿顶点的C—D环形链的构形，还有一类是不含以上任何一种环形链的构形。
BAB型的5—轮构形中，轮沿顶点间的对角链有A—C，A—D，B—C和B—D四种，邻角链有A—B，C—D，B—C和B—D四种，其中B—C和B—D既是对角链又是邻角链。
解决K—构形的着色问题，用的都是交换对角链的方法，在1879年已经由坎泊证明了，所有的K—构形都是可约的。而要解决H—构形的着色问题，则必须用交换邻角链的方法，把构形首先变成K—构形，然后再用交换对角链的方法，给这个K—构形进行着色。
解决第一类H—构形时，由于其中含有经过5—轮的1B，2A和3B三个相邻轮沿顶点的A—B环形链，把C—D链分隔成了互不连通的两部分，交换5—轮的4D和5C两个邻角顶点的颜色所构成的邻角链C—D，就可使构形变成K—构形而可约；解决第二类H—构形时，由于其中含有经过5—轮的4D和5C两个相邻轮沿顶点的C—D环形链，把A—B链分隔成了互不连通的两部分，交换5—轮的1B，2A和3B三个相邻轮沿顶点的颜色所构成的邻角链A—B，也可使构形变成K—构形而可约。解决第三类H—构形时，由于其中没有任何的环形链，只能交换既是对角链又是邻角链的B—C链和B—D链之一，使构形转型，使构形同样的也变成K—构形而可约。可见，解决三类H—构形时，都是用的交换邻角链的方法。至于如何对第三类H—构形施行邻角链的交换，使构形转秋成K—构形，请见《四色猜测更一般性的证明》一文。
可以看出，对角链的交换是用来空出颜色的，是用来解决K—构形的着色问题的；而邻角链的交换是用来改变构形类型的。交换A—B链和C—D链目的是把H—构形变成K—构形，而交换B—C链和B—D链的目的也是把H—构形变成K—构形，或都是变成其他H—构形的。对角链的交换就是坎泊交换，即K—交换，是专门解决K—构形的着色的；邻角链的交换就是我们现在用的交换（是否可以叫作H—交换），是专门解决H—构形的着色的。
邻角链的交换，既能变型，又能断链。交换A—B链和C—D链断的是两条连通且相交叉的A—C链和A—D链；交换B—C链和B—D链断的是两条相交叉的连通链的其中一条。所以把交换邻角链也叫做断链交换或转型交换。

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

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