△（G）=6且不含特殊图形的平面图的完备染色

张岩

【摘要】用xvef（G）分别表示图G的完备色数。本文证明：若△（G）=6的平面图G且不含有4-圈，5-圈，则xvef（G）≤△（G）+4。

【关键词】△（G）=6 平面图 完备色数

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

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

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

本文讨论的是完备染色问题。平面图G的一个完备染色是指一个映射ψ：V（G）∪E（G）∪F（G）→{1，2，…，k），满足对于任意不同的相邻或相关联的元素x，y∈V（G）∪E（G）∪F（G）都有ψ（x）≠ψ（y）。G的完备色数是指G有一个完备k-染色的数k的最小值。

文中未加定义的术语和记号请参阅文献[1].用V，E，Fδ和△分别表示平面图G的顶点集，边集，面集，最小度和最大度.设v是图G的一个顶点，于v相关联的边的条数叫做v的度数，记作d（v），若d（v）=k（d（v）≥k），则称v为一个k-点（≥k一点）。在平面图G中，面f∈F（G），用b（f）表示围绕面f的闭途径。把闭途径b（f）的长度称为面f的度，记为d（f），若d（f）=k（d（f）≥k），则称f为一个k-面（≥k面）。

若V∪E∪F中的元素能用k个颜色进行染色，使得相邻或相关联的元素都接受不同的颜色，则称G是k完备可染的，G的完备色数xvef（G）=min{kG是k-完备可染的}.

关于平面图的完备染色是Ringel（1965）提出的，Kronk和Mitchem猜想：对任何简单图G，xvef（G）≤△（G）+4.Borodin已在1993年证明了对于任意的平面图G：若△（G）≥12，Xvef（G）≤△（G）+2。并且后来他提出了一个问题，对于△（G）≤11的平面图G，能否找到完备色数的一个紧的上界，对于△（G）≥7的平面图G，Borodin证明了chvef（G）≤△（G）+4.对于△（G）≥6的平面图G，Dong证明了chvef（G）≤△（G）+5.本文证明：定理1：若△（G）=6的平面图G且不含有4，5-圈，则xvef（G）≤△（G）+4=10.

一、引理

设G是满足定理1但不是10-完备可染的且6（G）=|V|+|E|尽可能小的这样一个平面图，则不难证明：

引理1 G是2-连通的，从而δ≥2且G的每个面的边界都是圈。

引理2 设uv是G的一条边，若d（u）=2，则d（u）+d（v）≥8。即2-点只能与6-点相邻。

证明：假设d（v）≤6，且设u相邻的另一个点为w，由引理1可得G-{u）+{vw}是简单图，且是10-完备可染的，现在把vw的色染给uw，则依次可染上uv，u。

引理3 任意点u关联一个3面，则d（u）≥4

证明：假设存在点u，关联一个3面f，且d（u）=2，设与边uv关联的另一个面为f1，设与点u相邻的另两个点为v，w，则G-{u}是10-完备可染的，现在对G进行染色，把面{f∪f1}的颜色染给f1，则可依次可染上边uv，vw，面f，点u。假设存在点u，关联一个3-面f，且d（u）=3，设与点u相邻的另两个点为v，w，则G-{uv}是10-完备可染的，设与边uv关联的另一个面为f1，把面{f∪f1}的颜色染给f1，删去u的色，现在对G进行染色，则可依次可染上边uv，面f，点u。

引理4 若G内有一个5-面关联2个2-点，则G是11-完备可染的.

证明：假设存在一个5-面f，关联2个2-点u，v，则G-{u，v}是11-完备可染的，现在对G进行染色，可依次可染上面f，与u，v相关联的四条边，以及点u，v.

二、定理1的证明

其次考察面的新权：

3-面f：由引理3，f不关联2-点，3-点。即f关联三个≥4-点则由R1，R2，w'（v）=-3+3×1=0.≥6-面f：w'（f）≥0。

参考文献：

[1]J. A. Bondy， O. S. R. Murty. Graph Theory with Applica-tions[M]. New York：Macmillan， 1976.

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

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

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

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

[6]O.V. Borodin， Structure theorem on plane graphs with ap-plication to the entire coloring number [J]. Journal of graphtheory vol，1996， （23）.

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

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