（G）=8且不含4-圈的平面图的完备染色

打开文本图片集

◆摘  要：用xvef（G）分别表示图G的完备色数。本文证明：若[Δ]（G）=8的平面图G且不含有4-圈，则xvef（G）≤[Δ]（G）+4。

◆关键词：[Δ]（G）=8;平面图;完备色数

1引言

图论起源于一个非常经典的问题——柯尼斯堡（Konigsberg）问题。

1738年，瑞典数学家欧拉（Leornhard Euler）解决了柯尼斯堡问题。由此图论诞生。欧拉也成为图论的创始人。

1859年，英国数学家汉密尔顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即“绕行世界”。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题，从而引起广泛的注意和研究。

图论是门应用十分广泛且内容非常丰富的数学分支，它在生产管理，军事，交通运输，计算机网络等许多领域都有重要的应用。在图论的历史中，还有一个最著名的问题——四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。这一问题最早于1852年由Francis Guthrie提出，最早的文字记载则现于德摩根于同一年写给哈密顿的信上。包括凯莱、肯普等在内的许多人都曾给出过错误的证明。泰特（Tait）、希伍德（Heawood）、拉姆齐和哈德维格（Hadwiger）对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，Heiich Heesch发表了一个用计算机解决此问题的方法。1976年，阿佩尔（Appel）和哈肯（Haken）借助计算机给出了一个证明，此方法按某些性质将所有地图分为1936类并利用计算机，运行了1200个小时，验正了它们可以用四种颜色染色。四色定理是第一个主要由电脑证明的理论，这一证明并不被所有的数学家接受，因为采用的方法不能由人工直接验证。最终，人们必须对电脑编译的正确性以及运行这一程序的硬件设备充分信任。主要是因为此证明缺乏数学应有的规范，以至于有人这样评论“一个好的数学证明应当像一首诗——而这纯粹是一本电话簿！染色问题是图论的重要内容，也是图论的起源之一，具有重要的理论意义和实际意义。几百年来，它深深汲引着数学家们的注意力，图的染色问题又有很多种分类，如顶点染色，边染色，全染色，点面染色，边面染色，完备染色等等。关于平面图的染色问题一直是图论界的研究热点。

参考文献

[1]J.A.Bondy，U.S.R.Murty.Graph Theory with Applications[M].New York：Macmillan，1976.

[2]H.Kronk and J.Mitchem.A seven-color theorem on the sphere[J].Discrete Math，1973（6）.

[3]O.V.Borodin.The structure of edge neighborhoods in planar graph and the Simultaneous coloring of the vertices，edges and faces[J].Metem.Zametki，1993（53）.

[4]Wang Weifan.Upper bounds of entire chromatic number of plane graphs[J].Europ.J.Combinatorics，1999（20）.

[5]Daniel P.Sanders and Yue Zhao.On the entire coloring conjecture[J].Canad.Math.Bull.Vol，2000（43）.

[6]O.V.Borodin.Structure theorem on plane graphs with application to the entire coloring number [J].Journal of graph theory vol，1996（23）.

[7]吳建良.平面图的完备染色[J].山东矿业学院学报，1994（13）.

[8]王维凡.关于完备色数[J].辽宁大学学报，1995（22）.

推荐访问:平面图 不含 染色 完备