新浪博客

3—正则平面图的边色数与4—正则平面图色数的关系

2015-06-05 06:44阅读：

http://blog.sina.cn/dpool/blog/u/1638843823


3—正则平面图的边色数
与4—正则平面图色数的关系
雷 明
（二○一五年六月一日）

随顶点数的增加，3—正则图的面数与边数是一个什么样的关系呢。因为3—正则图的顶点数一定是偶数，所以3—正则图的顶点是每增2个，其面则增加了一个，边数增加了3条。因此，3—正则图的三大要素间的关系是：
最简单的3—正则平面图是K4，有4个顶点，4个面，6条边；
6个顶点的3—正则平面图有6个顶点，5个面，9条边；
8个顶点的3—正则平面图有8个顶点，6个面，12条边；
10个顶点的3—正则平面图有10个顶点，7个面，15条边；
…………
用公式表示出来则是:
3—正则图的顶点数是：V＝4＋2n（n≥0）
3—正则图的面数是：F＝4＋n（n≥0）
3—正则图的边数是：E＝6＋3n（n≥0）
塔特图的顶点数是V＝46，代入V＝4＋2n中得n＝21，再把n＝21代入F＝4＋n中得塔特图的面数F＝25，再把n＝21代入E＝6＋3n中得塔特图的边数是E＝69，与塔特图的三大要素的实际相符。
图1，a是一个有哈密顿圈的3—正则图，是可3—边着色的；图1，b是一个只有哈密顿道路的3—正则图，它虽是可3—边着色的，但必须通过一次由顶点③到顶点④的边二色（2和3）交换才能做到给边①和边②着上2色（如从图1，b到图1，c）。在上一篇文章《塔特图的各种着色和2—连通3—正则平面图是可3—边着色的证明》中的塔特图也是这样进行3—边着色的。
3—正则平面图的边色数与4—正则平面图色数的关系
 图2还是两个只有哈密顿道路的3—正则图，它们都是可3—边着色的，但都必须经过边二色交换也才能做到。与塔特图的着色方法也是一样的。
3—正则平面图的边色数与4—正则平面图色数的关系
 我们如果把有哈密顿回路（圈）和有哈密顿道路的图统一都叫做是可哈密顿的图，则图1和图2中的几个图就都是可哈密顿的，塔特图也可以说是可哈密顿的。当年的泰特认为所有3—正则平面图都是可哈密顿的，是否就是从这个意义上去说的，我们不清楚。但是否还有3—正则平面图是既没有哈密顿圈，又没有哈密顿道路，我们也不清楚。还需要进一步的证明。请大家找一找是否还有。
如果说再没有不可哈密顿的3—正则平面图了，那么所有的3—正则平面图就都是可哈密顿的，也都是可3—边着色的。其实3—正则平面图是否可3—边着色与其是否是可哈密顿并没有什么直接的关系。因为图的边着色就是给图的线图的顶点着色，而3—正则平面图的线图本身就是一个密度是3的4—正则平面图，该图的色数最小是3；图中的轮最大只可能是4—轮，没有奇轮，色数最大也只是3。这就决定了只要是3—正则的平面图，不管其是否可哈密顿，都是可3—边着色的。
如果能从3—正则平面图的可3—边着色，证明3—正则平面图（地图）也都是可4—面着色的，就可以证明任何地图都是可4—面着色的。这样也就可以使得地图四色猜测得到证明是正确的。因为给地图的面的染色正好就是给其对偶图——极大图——的顶点着色，任何地图是可4—面着色的，则任何极大图也就是可4—着色的。那么通过对极大图减边或去点所得到的任意平面图也就是可4—着色的。但我认为这个证明不那么容易。
3—正则平面图的边着色就是对其线图的顶点着色，其线图又是一个4—正则的平面图，那么这个由可3—边着色的3—正则平面图的线图构成的4—正则平面图也一定是可3—着色的。现在的问题是4—正则的平面图肯定不能说都是可3—着色的，图3就是一个不可3—着色的4—正则平面图。而这个图并不是某个对应的3—正则图的线图，当然它就不可能是可3—着色的了。从这里可以看出，4—正则平面图中可3—着色的图，一定有一个3—正则图的线图与其相同，而不可3—着色的4—正则平面图则一定没有3—正则图与之对应。从3—正则平面图的边数公式E＝6＋3n（n≥0）中可以看出，其边一定是3的倍数，而图3中的这个4—正则平面图的顶点数却是11，不是3的倍数，所以它不是某个3—正则图的线图，也就不是可3—着色的了。
3—正则平面图的边色数与4—正则平面图色数的关系
 雷 明
二○一五年六月一日于长安

注：该文已于二○一五年六月五日在《中国博士网》上发表过，网址是：
http://www.chinaphd.com/cgi-bin/topic.cgi?forum=5&topic=2551&show=0

我的更多文章

下载客户端阅读体验更佳

APP专享