回答广西的增勇朋友

雷明85639720

回答广西的增勇朋友：

以下是我未出版的《四色问题与欧拉公式》一书中的一节：

42、赫渥特图的4—着色

现在用坎泊创造的颜色交换法，对Heawood—图进行4—着色如下（关于Heawood—图的4—着色，本读物作者早已于1989年着色成功，并于1992年3月8日在陕西省数学会第七次代表大会暨学术年会上作过学术报告，地点是在西安东郊的中国人民解放军空军工程学院（现已改为中国人民解放军空军工程大学））。为了说明问题方便我们把Heawood—图（图4—3）再次画到这里。
Heawood—图是一个只有一个顶点未着色的图，其它的顶点都已着上了b（兰）、r（红）、g（绿）、y（黄）四种颜色之一，待着色的顶点V处在一个5—轮构形的中心顶点，其围栏顶点已用完了四种颜色。该图中有一条由顶点2到顶点4的连通的b—g链，也有一条由顶点2到顶点5的连通的b—y链（两链又有交叉点即两链共有的顶点2和8，均着b色），即就是对这两条链进行了颜色交换，也不能空出颜色给V 。只所以空不出颜色来，就是因为这两条链均是连通链。另外图中还有一条由经过顶点4、5、7、6，再经过了一系列的顶点后，又返回到顶点4的环形的g—y链，即一个圈（图中加粗了的边）。这条环链把b—r链分成了环内环外互不相连通的两部分，交换一部分b—r链的颜色不但不会影响到g—y链的颜色，而且也不会影响另一部分b—r链上各顶点的颜色。

1、第一种着色方法：先从g—y环链外面的一支b—r链进行交换
这种方法第一次交换是从b—g和b—y两交叉链的一个交叉顶点8开始进行b—r链的交换。
现在就从顶点8开始进行b—r链的交换，这时顶点8变成了r色，如图4—7，使上述的b—g链和b—y链变得由顶点2到顶点4和由顶点2到顶点5不连通，使图变顾了如第36节中的图4—1，n类型的图。虽然图中仍有r—g、r—y与两条交叉且连通的链，但可从顶点2开始进行b—g链或b—y链的交换，均可空出b给V着上，如图4—8和图4—9；或从顶点4开始进行b—g链的交换，空出g给V着上，如图4—10；或从顶点5开始进行b—y链的交换，空出y给V着上，如图4—11。注意，这时不能再从原两交叉链的交叉顶点2进行交换了。


2、第二种着色方法：先从g—y环链里面的一支b—r链进行交换
这种方法第一次交换是从b—g和b—y两交叉链的另一个交叉顶点2开始进行b—r链的交换。
如果从顶点2先进行b—r链的交换，使顶点2变成r色，如图4—12，也可使以上的b—g链和b—y链变得由顶点2到顶点4和由顶点2到顶点5不连通，也使图变成了一个如第36节中的图4—1，n类型的图，虽然图中还有两条连通且交叉的b—g、b—y链，可再进行一次别的链的交换后，给V着上r、g、y三种颜色之一。如图4—13。图4—13，a是从顶点4开始交换g—r链后，空出g给V的；图4—13，b则是从顶点5开始交换y—r链后，空出y给V的；而图4—13，c和图4—13，d则是从顶点2开始分别对g—r链和y—r链进行交换的，都空出了r给V着上。


Heawood—图中的顶点V通过使用坎泊创造的颜色交换技术交换某些顶点的颜色后，是可以给其着上已使用过的四种颜色中的任何一种，所以说Heawood—图是一个4—色图，是可4—着色的。
3、第三种着色方法：对r—y链和r—g链同时进行交换
这种方法是首先相继交换两条关于r的链，目的是想同时移去两个r，空出r给V着上。

Heawood—图与前面第36节《用坎泊创造的颜色交换技术对猜测进行证明》一节中的图4—1，n的情况基本是一样的，并和该节中的图4—2，n的情况完全相同，也是在环形的g—y链的顶点4（着g色）和顶点6（着y色）之间多了一些顶点。上面给Heawood—图的着色方法与给图4—1，n中的顶点V着色的方法和步骤是完全相同的。既然Heawood—图与图4—2，n的情况完全相同，那么应该说是可以用给图4—2，n中的顶点V的着色方法的，即先从顶点3开始对r—y链进行交换，再从顶点1开始进行r—g链的交换，就应可以空出r色给V着上。但是实际上仍是空不出颜色的（如图4—14，a，b）。这是为什么呢？是因为Heawood—图比图4—2，n的图要复杂得多，在从顶点3开始对r—y链进行了交换后，使得顶点4与顶点6之间的g—y链中的y都变成了r，的确也破坏了环形的g—y链的连通性，但又在顶点4和顶点6之间新产生了一条r—g链，该链且与从顶点1到顶点7的r—g链相连通（图中加粗了的边），使得在再从顶点1进行r—g链的交换时，顶点4的颜色由g又变成了r，r仍不能空出。虽没有移去两个r，但却也使图变成了与图4—1，o相类似的图了。这时再用与给图4—1，o相同的方法再进行两次关于y的链的交换，即可能空出一种颜色y给V着上（如图4—14，c，d）。但要注意的是必须先从顶点5开始进行y—b链的交换，后从顶点3开始进行y—g链的交换，才能空出y给V，否则是不能空出颜色给V的。同样我们还可以看到，在从顶点3进行了关于r—y链的交换后，图已经就变成了图4—1，o形式的图了，同样也可以先从顶点5开始进行y—b链的交换，后从顶点3开始进行y—g链的交换，也能空出y给V。
以上对赫渥特图的第一种和第二种着色方法，实质上是从两交叉链的交叉顶点进行交换的，交换后达到了破坏两链连通性的目的，使图变成了一个没有连通链的图，着色时就方便多了。这种方法可以叫做“断链”着色法（见下一节第43节《对赫渥特图的分析》一节中的“7、断链的着色法”一段。

以上给Heawood—图着色的方法只是其中的几种，当然还有多种其它的方法，Heawood—图也还有多种4—着色的模式，这里也不可能一一列举出来。在后面的第八章《常见图及其图值函数的着色》一章中的第102节《赫渥特图的又一4—着色模式》一节中将会对Heawood—图再给出另外一种4—着色模式。

由于1992年那时还没有多媒体，所以我在西安空军工程学院作学术报告时，还是用手直接在黑板上画图，画图就占用了一定的时间。所以我在报告时主要只是用了以上第一种方法对Heawood—图进行了4—着色表演，后面的两种方法只是说了一下，并没有画图。整个报告连画图在内，只用了不到半个小时。

雷明，2017，6，29，晚9点13分于长安

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，