无环形链的H—构形的4—着色（二）

雷明85639720

无环形链的H—构形的4—着色（二）
雷  明
（二○一九年七月二十五日）
（我在这里发不上图，请到＜中国博士网＞中去看）

关于有经过构形围栏顶点的环形链的BAB型的H—构形，我们可以通过断链交换，交换环形链内外的任一条与环形链是相反色链的链，使图转化成不存在连通的A—C链和A—D链的K—构形而可约。但是，无环形链的H—构形就只能用转形交换法解决了。
这里首先明确一下，我所说的H—构形是指不但含有连通且相交叉的A—C链和A—D链，而且同时又是不能连续的移去两个同色B的构形。另外我所说的交换是只交换处在一条链上的顶点的颜色，而不是交换处在某一环（一条连通链与待着色顶点所构成的圈）的某一侧的所有与构成环的连通链的颜色不同的顶点的颜色。

图1是一个无环形链的H—构形，他具有以上我说的H—构形的特点。不但含有连通且相交叉的A—C链和A—D链（如图2），而且从顶点1开始交换了B—D链后，就会生成从顶点3到顶点5的连通的B—C链（如图3），从顶点3开始交换了B—C链后，又会生成从顶点1到顶点4的连通的B—D链（如图4），不能连续的移去两个同色B。所以它是一个地地道道的H—构形。图中又没有经过构形围栏顶点的环形链，A—C链和A—D链均是直链，且各只有一条（如图5和图6）。由于图5和图6只是左右结构上的不同，实质上是同一个（类）构形，所以我们就只研究图5就可以了。

现在我们对图1进行逆时针转型交换如下：
第一步，对图1从顶点1开始交换B—D链，得到的图7（也就是是图3）中生成了从顶点3到顶点5的连通的B—C链。图转化成一个DCD型的H—构形。
注意：如果是把处在A—C—V环外侧的B色和D色的顶点都交换颜色，则这个交换后的图就是一个K—构形，因为交换后生不成从顶点3到顶点5的连通的B—C链。但我们这里主要是想看一看无环形链的H—构形，道底能在几次转型交换内解决问题，所以我们还是只交换了处在同一条B—D链上的顶点的颜色。

第二步，对图7从顶点5开始交换D—A链，得到的图8中没有生成从顶点1到顶点3的连通链D—B，应该项说问题已经可以解决。但在平面图范围内还可以构造从顶点1到顶点3的D—B连通链（如图9），这是一个ABA型的H—构形。

第三步，对图9从顶点2开始交换A—C链，得到的图10中也没有生成从顶点4到顶点1的连通链A—D，问题也应得到解决。同样的，在平面图范围内也还是可以构造从顶4到顶点1的连通的A—D链的（如图11），这是一个CDC型的可以连续的移去两个同色C的K—构形，而不再是H—构形了。
第四步，对图11从顶点5交换C—B链，得到的图12中虽没有生成从顶点2到顶点4的连通链C—A，但在平面图范围内再不可能构造从顶点2到顶点4的连通链C—A了，因为其前面有一条相反的色链B—D在阻隔着，C—A链是不可能通过的。很明显的是一个只有一条连通的B—D链的K—构形了。

第五步，对图12再从顶点2交换C—A链，就连续的移去了图10中的两个同色C，把C给待着色顶点V着上（如图13）。着色结速。

以上只进行了三次转型，加上最后的两次交换，共计五次交换。这就是无环形链的H—构形（张彧典先生叫Z—构形）的最大交换次数。若图由图1的任意的图变成极大图时，则交换的次数将会更少。图1 （也就是图5）是按逆时针转型的，若按顺时针转型，也会得出同样的结论（如图14到图20）。请读者自已试一试。

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

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

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

晋源泉

交换的真累，我都累的快垮了。

雷明85639720

想研究出成果来，没有这一点耐力是不行的!