给12341234数字先生提出的图的着色

雷明85639720

给12341234数字先生提出的图的着色
雷  明
（二○一五年八月十七日）

这位数字先生提出的图是王树禾先生的《图论》书第99页中的图5.16，是一个用以代替5—轮构形的有4个待着色顶点（其实构形中只可能有一个待着色顶点，因为着色到最后还是只有一个待着色顶点的构形）的所谓构形，现在我给它着色如下，请12341234这位数字先生好好的看一看。
这个构形的围栏顶点有6个，待着色顶点有4个，都是5—度顶点。如图1，a。6个围栏顶点占用完了四种颜色的着色模式分别有以下两种情况：有一种颜色用了三次的情况和有两种颜色分别用了两次的情况。由于这个图（构形）具有左右的轴对称性，所以这后一种情况中又有4种着色模式。因此6个围栏顶点占用完了四种颜色的着色模式共有5种，即图1中的b，c，d，e，f图。图中顶点的名称用带圈的数字表示，所着颜色用不带圈的数字表示。

1、对于图1，b的构形，我们首先可以分别给顶点⑨⑧⑩着上颜色2，3，4，这时只剩下一个以顶点⑦为待着色顶点的5—轮构形，如图2，a。该构形的顶点⑥⑧着色3，其他顶点⑩①②分别着色4，1，2，围栏顶点已占用完了四种颜色。从最复杂的情况考虑，若顶点⑩—①和⑩—②分别有连通的4—1链和4—2链，且两链又相交叉（所谓最复杂的情况就是赫渥特图那样的情况），如图2，b。从两交叉链的任一个交叉顶点（着色为4，本交换是从带圈的那个交叉顶点开始的）进行3—4链的交换，使两交叉链均变得不连通，如图2，c。再从顶点①（或顶点②）开始进行1—4链（或2—4链）的交换，空出了颜色1（或颜色2）给顶点⑦着上，如图2，d。也可以从顶点⑩开始进行1—4链或2—4链的交换，空出颜色4给待着色顶点⑦着上。着色完成。

2、对于图1，c的构形，首先可以分别给顶点⑨⑧⑩着上颜色1，3，4，只剩下一个以顶点⑦为待着色顶点的5—轮构形，如图3。该构形的顶点②⑥均着1色，顶点①⑧均着3色，顶点⑩着4色，围栏顶点只点用了1，3，4三种颜色，把第四种颜色2给待着色顶点⑦直接着上即可。着色完成。

3、对于图1，d的构形，首先可以分别给顶点⑨⑧⑩着上颜色3，1，2，也只剩下一个以顶点⑦为待着色顶点的5—轮构形，如图4。该构形的顶点①⑧均着1色，顶点②⑩均着2色，顶点⑥着3色，围栏顶点也只点用了1，2，3三种颜色，把第四种颜色4给待着色顶点⑦直接着上即可。着色完成。
4、对于图1，e的构形，首先可以分别给顶点⑨⑧⑩着上颜色3，1，4，只剩下一个以顶点⑦为待着色顶点的5—轮构形，如图5，a。该构形的顶点①⑧着1色，其他顶点②⑩⑥分别着2，4，3色，围栏顶点也占用完了四种颜色。也从最复杂情况考虑，若顶点②—⑩和②—⑥分别有连通的2—4链和2—3链，且两链又相交叉，如图5，b。从两交叉链的任一个交叉顶点（着色为2，本交换是从带圈的顶点⑤开始的）进行1—2链的交换，使两交叉链均变得不连通，如图5，c。再从顶点⑩（或顶点⑥）开始进行2—4链（或2—3链）的交换，空出了颜色4（或3）给待着色顶点⑦着上，如图2，d。也可以从顶点②开始进行2—4链或2—3链的交换，空出颜色2给待着色顶点⑦着上。着色完成。

5、对于图1，f的构形，首先可以分别给顶点⑧⑩着上颜色3，4，剩下的分别是以顶点⑦和顶点⑨为待着色顶点的两个5—轮构形，两个5—轮构形的围栏顶点均占用完了四种颜色。如图6，a。

首先看以顶点⑨为待着色顶点的构形，从最复杂情况出发，若构形中有顶点⑤—③和⑤—⑧的连通的1—3链和1—2链，且两链在顶点②处又相交叉，如图6，b。从交叉顶点②开始交换1—4链，使两连通链均断开，如图6，c。再从顶点③（或⑧）开始进行1—2（或1—3）链的交换，空出了颜色2（或3）给待着色顶点⑦着上，如图6，d。也可以从顶点⑤开始进行1—2链或1—3链的交换，空出颜色1给待着顶点⑨着上。
现在图中就只剩下一个顶点⑦没有着色，这是一个5—轮构形的待着色顶点。但在前面通过给顶点⑨的着色已使顶点⑦这个5—轮构形的围栏顶点所占用的颜色由图6，b中的四种减少到了图6，d中的2，3，4三种，把颜色1直接给待着色顶点⑦着上就可以了，如图6，e。着色完成。
到此，王树禾先生的《图论》一书中的图5.16这一种构形就着色完毕。
由于这个构形中有多个待着色顶点，所以不同的人的着色，同一个人不同时间对其着色，其着色的顺序可能都是不同的，所以该构形的4—着色模式一定还有很多种，并不只是以上的5 种。在这里我也不可能把各种情况都一一做出。
通过对这个构形的着色，使我更加坚定了“一个构形只有一个待着色顶点”的观点。待着色顶点多了，就得一个一个的去着色，最后剩下的只可能是一个，把这个最后的待着色顶点着上图中已用过的四种颜色之一时，也就证明了这个多待着色顶点的构形是可约的。                                                                                                                                                                                            

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

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