再论3—正则平面图的可3—边着色问题

雷明85639720

再论3—正则平面图的可3—边着色问题
雷  明
（二○一五年五月二十九日是）

我在前几于写了一篇题为《塔特图的各种着色及2—边连通3—正则平面图是可3—边着色的证明》的文章，有网友“11223344”回复道，把范益政等翻译的《图论导引》一书中第117页中的图6.2的顶点v1和v3，v3和v5，v5和v10，v10和v1之间分别再用一条边连接后，图6.2就成了4—正则平面图 G。这时，图G的顶点并不是3—着色的啊！”并说，4—正则平面图并不一定都是3—着色的（原回复贴在我回复他后他就就删去了），我当时回复说：“这位数字朋友，我在这一文章中得到的是“3—正则平面图是可3—边着色的”，并没有得到结论说4—正则平面图的顶点是可3—着色的。至于3—正则平面图的可3—边着色问题，我就是这样证明的：它的边着色就是对其线图的顶点着色，该线图是一个密度是3的、且是4—正则的平面图。因为其密度是3，所以其着色时，一定得用3种颜色，又因为该线图中没有轮，所以也不可能用到第四种颜色。即于这两点我就可以断定无桥的3—正则的平面图的边色数都是3 ，即都是可3—边着色的。虽然3—正则平面图的线图是一个4—正则的平面图，但它只是4—正则平面图中的一种，我也没有说所有4—正则平面图的顶点着色的色数就是3，而只是通过3—正则平面图的线图的顶点着色数是3，来说明3—正则平面图的边色数一定是3的。你是不是把我的文章还没有看明白呢。雷明”。这位朋友又回复：“为什么你说‘该线图是一个密度为 3 的’，其根据何在？我在上边回复中所说的‘图G’的密度，又该是多少呢？”我又回复说：“朋友，图的密度就是图中最大团的顶点数。我那个3—正则图的线图中的最大团是K3，有3个顶点，那么它的密度就是3。你指出的那个4—正则图中的最大团也是K3，其密度也就是3。不过你这一提醒，我真的得要考虑我说的3—正则图的线图的色数的证明是否完备的问题。你提出的这个图，按我的理论，色数应是3，但实际上其着色却必须用四种颜色。这就不得不使我还要进一步重审用我的理论对平面图着色数色的判断方法了。”以后他再也没有回复，只是把他的有关贴子删掉了。
泰特认为可哈密顿的3—正则平面图是可3—边着色的，图中一定是有一条哈密顿回路的，这样的图3—边着色是没有问题的。因为哈密顿回路是经过了图中所有的顶点，又回到了原始起点的回路（圈），这是一个边二色圈且是一个偶圈，这个偶圈一定是二色的。把这个边二色圈外的其他边均着上第三种颜色，一个可哈密顿的3—正则图的边着色就已完成，图中只用了三种颜色。但一个非哈密顿的3—正则平面图中虽然有哈密顿道路，但不是哈密顿圈（回路），这条道路虽是边二色的，但该边二色道路以外的其他边不是都可以直接着上第三种颜色的，最后的待着色边的着色，还必须通过边颜色交换空出颜色后，才能着上三种颜色之一，如塔特图边着色那样。但所有的非哈密顿的3—正则图，最后的待着色边，是否都可以通过颜色交换空出颜色给其着第三种颜色，这还须进一步的证明。所以还不能直接下结论说“只要是3—正则的平面图（地图）都是可3—边着色的。”非哈密顿的塔特图的边着色结果虽是3 色的，但最后的色图中虽也有一条边二色回路1—2圈，但没有走完图中所有的顶点，也就说明了塔特图是非哈密顿的。
3—正则平面图的边着色就是对该图的线图的顶点着色。其线图的三大要素与原图的三大素的关系是：
线图的顶点数v线＝原图的边数e原
线图的面数f线＝原图的顶点数v原＋原图的面数f原
线图的边数e线＝线图的顶点数v线＋线图的面数f线－2
＝原图的边数e原＋原图的顶点数v原＋原图的面数f原－2


一个K4图（也是3—正则图）与它的线图如图1所示。K4图的v＝4，f＝4，e＝6，其线图的顶点数v线＝K4图的e原＝6，面数f线＝K4图的v原＋K4图的f原＝4＋4＝8，边数e线＝线图的v线＋线图的f线－2＝6＋8－2＝12。与图中实际相符。
塔特图的顶点数是46，面数是25，边数是69。它的线图的顶点数是69，与原图的边数69是相同的，线图的面数是71，也正好是原图顶点数46与面数25的和。
“11223344”朋友说的那个图如图2。这个图虽然也是一个4—正则图，但它是不是就是某个3—正则图的线图呢，不一定。所以说，3—正则图的线图虽是一个4—正则图，但4—正则图却不一定也就是非得从某一个3—正则图作线图而得的。图2的这个图就是这样。

图2中的图的顶点数是v＝11，面数是f＝13，边数是v＝22。如果它是某一个3—正则图的线图，那么这个3—正则图的边数就是图2的顶点数11，图2这个4—正则图的面数13就应是这个3—正则图的顶点与面数之和。两数相加之和为13的可能组合是1和12，2和11，3和10，4和9，5和8，6和7，7和6，8和5，9和4，10和3，11 和2，12和1。这些组合中我们把前一个数字看作是3—正则图的顶点数，把后一个数字看作是3—正则图的面数。由于3—正则平面图的边数等于3倍的顶点数再除以2，并且这里的得数应是11（上面已知道该3—正则图的边数是11）。但在上面的各组合中，前一个数的3倍除以2所得到结果中并没有11这个数，一个组合也达不到这一要求；另外以这些组合中的顶点数所能画出的3—正则平面图的边数也不是11，面数加顶点数也不是13。所以图2 的图并不是由哪个3—正则平面图的线图而得的，只是一个普通的4—正则图而已。所以它的顶点能不能3—着色，与3—正则图的线图的顶点能不能3—着色是没有任何关系的。
不过“11223344”朋友的这一提醒使我联想到一个问题。图2中的确没有轮，密度是3，但其色数却是4，而是大于3的。使我觉得我提出的判断平面图的色数中的一条，即“无轮的图的色数一定是小于等于3的”这一结论是否正确的问题。同样也对3—正则平面图是否都是3—边着色的问题有了怀凝。我的上述判断方法是否正确，是不是所有3—正则平面图都是可3—边着色的还有待于再进一步的研究。

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

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，