再谈平面图着色中的“构形”概念

雷明85639720

再谈平面图着色中的“构形”概念
雷  明
（二○一五年八月二日）

在平面图的着色与四色猜测的证明中，经常遇到“构形”与“不可免构形”的概念。那么什么是构形和什么是平面图的不可免构形呢，到现在可能还没有一个统一的说法。我在这里想谈谈个人的看法。
1、什么是“构形”与平面图的不可免集
我认为在平面图的着色与四色猜测的证明过程中所说的“构形”并不是一个具体的图，而是一个只剩一个顶点未着上图已用过的四种颜色之一的顶点数是任意多的非具体的图。
“构形”中的未着色顶点可以着上图中已用过的四种颜色之一时，这个构形就是“可约”的，否则就是不可约的。
已知任何平面图中至少存在着一个顶点的度是小于等于5的，那么就是说度小于等于5的顶点在平面图中是不可避免的，即这种度小于等5的顶点在平面图中至少也要存在一个的，不可能没有。
度小于等于5 的顶点与其相邻的顶点在平面图中所能构成的关系最复杂的分子图最多只能是一个轮。当这个轮的中心顶点未着上颜色而图中所有顶点均已着上四种颜色之一时，这就是一个构形。我们把轮沿顶点（即所谓的围栏顶点）以外的其他所有顶点都去掉时，剩下的就是一个轮图。这个轮图就是平面图的不可免构形。
平面图有多少个不可免构形呢，这是一个很关链的问题，必须弄清楚。度小于等于5的顶点一共有6种，也即平面图有6种不可免的构形——即6种不可免的轮：即0—度顶点（如孤立顶点K1图，也即0—轮），1—度顶点（如K2分子图的一个顶点，也即1—轮），2—度顶点（如有一条平行边的2—重K3分子图中的一个非引出平行边的2—度顶点，也即2—轮），3—度顶点（如K4分子图的一个3—度顶点，也即3—轮），4—度顶点（即4—轮的中心顶点）和5度顶点（即5—轮的中心顶点），共六种。
对平面图着色时，只要把这6种轮中的任一个轮的中心顶点作为待着色顶点时，这才是一个不可免构形。所以平面图的不可免构形集就是由以上六种构形构成的。
看来，证明四色猜测是否正确，只要证明这六种构形中的待着色顶点是可约的，就可得到四色猜测是正确的结论。电子计算机找了近2000个构形是没有必要的。
2、各不可免构形的着色方法
0—轮构形到4—轮构形，坎泊已经证明是可约的了。他也证明了5—轮中的两条连通链只有一个相交顶点时的情况是可约的。而赫渥特却构造出了5—轮构形中两条连通链有两个相交顶点时的这一情况，在坎泊的证明中是没有的。当时坎泊和赫渥特两人都不能给其中的待着色顶点着上图中已用过的四种颜色之一。赫渥特的这个图到底能否4—着色，现在已有许多人都能对其进行4—着色了，这里不再多叙。
5—轮构形中存在两条连通链有两个相交顶点的情况一共有三种情况，我们用5—轮轮沿顶点上着有B夹A（BAB型）的一种为例来进行说明：
一是构形中除了连通的A—C链和A—D链有两个相交顶点（均着A色）的两条链外，还有一条环形的A—B链。这种情况，可以不分先后次序的交换两条关于两个同色B的链（如B—C或B—D链），就可移去颜色B，给待着色顶点着上，该构形可约；
二是构形中除了连通的A—C链和A—D链有两个相交顶点（均着A色）的两条链外，再没有任何环形链，A—B和C—D链都是直链。这种情况，可以有选择的先交换一条关于B（如B—C链或B—D链）的链，后交换另一条关于B（如B—D链或B—C链）的链，空出颜色B给待着色顶点，该构形也是可约的。张彧典先生的第一个、第三个、第四个、第五个、第六个、第七个构形都可以这样来着色，这几个构形都不是赫渥特构形类的构形，因为他们都可同时移去两个同色；
三是构形中除了连通的A—C链和A—D链有两个相交顶点（均着A色）两条链外，有一条环形的C—D链，它把A—B链分隔成环内环外互不连通的两部分。这种情况下，交换其中任一条A—B链，都可使原有的连通的A—B链“断链”，变成不连通的。这样就可以再使用一次坎泊的颜色交换技术，空出一种颜色给待着色顶点着上。这就是张彧典先生的第二个构形；
第三种情况才是赫渥特构造的图的情况。不能同时移去两个同色。这种情况中还有三种不同的情况：
一是米勒构造的图，即M—构形。图中既有环形的A—B链，又有环形的C—D链，既有A—B直链，也有C—D直链。两条相同的链均被另外一条不同的环链分隔为环内、环外两部分。交换其中任一条C—D链后，均可使A—C链和A—D链断开，使构形变成可同时移去两个同色B的构形。这就是张彧典先生的第九构形；
二是我构造的图，我叫它L—构形。图中只有环形的A—B链，也把C—D链分成了两部分。同样交换其中的任一条C—D链后，均可使A—C链和A—D链断开，使构形变成可同时移去两个同色B的构形。这一构形张彧典先生的构形中是没有的；
三是张彧典先生构造的图，我叫它Z—构形。图中没有任何环链，又不能同时移去两个同色。只能交换任一条关于两个同色的链（如B—C链或B—D链），把构形变成别的构形，再给待着色顶点着色。这就是张彧典先生的第八个构形。
3、结论
现在看，张彧典先生说类赫渥特构形的构形只有九种（张先生把它叫做H构形不可免集），而实际上现已发现的只有以上四种。是否还有别的类赫渥特构形的构形呢，谁也不能下结论。因此，用这样的“着色法”证明四色猜测是不可能得出最终结论的，要得出最终结论必须走不画图不着色进行证明的道路。

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

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

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,,