H—构形着色时的最大交换次数是5

雷明85639720

H—构形着色时的最大交换次数是5
雷  明
（二一八年十二月二十七日）
（在这里我发不上图，请到《中国博士网》中去看）

平面图H—构形是不能空出任何颜色的给待着色顶点的构形。对于BAB型的H—构形，可按其中A—B链和C—D链的结构，可把H—构形分成三个类型。第一类（如图1），是图中有经过连续相邻的三个围栏顶点的环形A—B链的构形，第二类（如图2），是图中有经过相邻的两个围栏顶点的环形C—D链的构形，第三类（如图3和图4），是上述的任何环形链都不存在的构形。第一类构形交换经过相邻的两个围栏顶点的C—D链，图就变成K—构形而可约；第二类构形交换经过连续相邻的三个围栏顶点的A—B链，图也就变成了K—构形而可约。最多都只用了三次交换。

在图3和图4的第三类构形中，各有两个加大了的4—度顶点，各分位于A—B链和C—D链上。若把其中任一个顶点的颜色改成与其相反的色链中的颜色，则该图就会变成有环形链A—B的第一类构形，或者变成有环形链C—D的第二类构形。都成为可约的构形。总共的交换次数是4。但是，这种有4—度顶点的构形，并不是所有的第三类构形都具备，所以还得要用别的证明方法再进行证明。

第三类H—构形中，A—B链和C—D链都不是环形的，所以A—B链和C—D链都不能交换，那么，也就只能进行转型交换了。然后再根据转型后的构形类型进行解决。图3和图4正好是左右相反的构形，实际上是同一个构形，所以只要研究图3一个就行了。这里要注意的是，图3中除了顶点1—2—3—4—5—1间和6—7间的边是单条边外，其他各边都可以是链。所以在交换了一个关于两个同色的链后，可以尽量的构造从另一个同色顶点到其对角顶点的连通链，直到在平面图范围内不可能再连通为止。
对图3从顶点1B开始交换B—D链后，生成从顶点3B到其对角顶点5C的连通链B—C（如图5），再从顶点4D开始交换D—A链，可以生成从顶点1D到其对角顶点3B的连通链D—B（如图6），再从顶点2A开始交换A—C链，也可以生成从顶点4A到其对角顶点1D的A—D链（如图7），再从顶点5C开始交换C—B链，就再不可能生成从顶点2C到其对角顶点4A的C—A连通链（如图8），所以说前面的图7已经是一个可以连续的移去两个同色C的K—构形了。再对图8从顶点2C开始交换C—A链，就可以空出C给待着色顶点（如图9）。总共是进行了五次交换。

转型交换还可以从两个同色顶点B进行。把以上从顶点1B开始的交换叫逆时针转型交换，把从顶点3B开始的交换叫顺时针转型交换。对图3从顶点3B开始交换B—D链后，图就变成了CDC型的有经过顶点1B和2A两个围栏顶点的环形A—B链的第二类可约构形（如图10—1）。再进行两次交换就可空出颜色来。总共只进行了三次交换。

虽然如此，但却也生成了从顶点1B到其对角顶点4D的连通链B—D（如图10—2）。

若对图10继续从顶点5C开始交换C—A链的转型交换时， 可以生成从顶点3C到其对角顶点1B的连通链C—B（如图11），再从顶点2A开始交换A—D链时，不可以生成从顶点５A到其对角顶点3C的A—C链（如图12），这说明前面的图11已经是一个可以连续的移去两个同色A的K—构形了。再对图12从顶点5A开始交换A—C链，就可以空出A给待着色顶点（如图13）。总共只交换了四次。这里交换次数是4正好说明了第二类构形也是可以经过三次转型交换解决问题的。

若对图4也象图3一样，进行两个方向的转型交换，也会得到同样的结果。
以上几种交换中，交换次数分别是3、4、5，最小的是3，最大的是5。这就证明了H—构形着色时的最大交换次数是5。由此可以看出，H—构形着色时的交换次数一定是大于等于3而小于等于5的。
1891年赫渥特构造的赫渥特图属于第二类构形，其交换的次数是3；1990年前后敢峰和米勒构造的敢峰—米勒图属于第一类构形，其交换的次数也是3；1994年张彧典先生构造的第八构形属于条三类构形，其交换的次数也是3；只有1935年美国人Iirving Kittell构造的有对称轴的图，也属于第三类构形，其交换的次数最大，只是5，但也没有大于5。

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

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