Δ(G)=11且不含有三角形,4-圈的平面图的完备染色

上官敏乐

（浙江树人大学 基础部，浙江 杭州 310015）

引言

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

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

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

在图论的历史中，还有一个最著名的问题－－四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。这一问题最早于1852 年由Francis Guthrie 提出，最早的文字记载则现于德摩根于同一年写给哈密顿的信上。包括凯莱、肯普等在内的许多人都曾给出过错误的证明。泰特(Tait)、希伍德(Heawood)、拉姆齐和哈德维格(Hadwiger)对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969 年，Heinrich Heesch 发表了一个用计算机解决此问题的方法。1976 年，阿佩尔(Appel)和哈肯(Haken)借助计算机给出了一个证明，此方法按某些性质将所有地图分为1936类并利用计算机，运行了1200 个小时，验正了它们可以用四种颜色染色。四色定理是第一个主要由电脑证明的理论，这一证明并不被所有的数学家接受，因为采用的方法不能由人工直接验证。最终，人们必须对电脑编译的正确性以及运行这一程序的硬件设备充分信任。

本文讨论的是完备染色问题。文中未加定义的术语和记号请参阅文献[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 的完备色数χvef(G)=min{kG 是k-完备可染的}.Kronk 和Mitchem[2]猜想:对任何简单图G,χvef(G)≤△(G)+4.Borodin[3]已证明：若△(G) ≥12，χvef(G)≤△(G)+2。本文证明:

定理1:若△(G)=11 的平面图G 且不含有三角形,4-圈,则χvef(G)≤△(G)+2＝13.

图G 的一个完备色列表是一个颜色集合簇L，对G 的每个元素x∈V ∪E ∪F 都配一个颜色集合L（x）.若G 一个正常完备染色φ(x)，使得每个元素，则称G 是L 全可染的。若对每一个满足能，x∈V ∪E ∪F 的完备色列表L,G 都是L 完备可染的，则称G 是k 完备可选择的，G 的列表完备色数，或称完备选择数chT(G)是使得G 是k 完备可选择的最小的非负整数k.

一、引理

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

引理2 2－点只能与11－点相邻。

证明：假设2－点与点v 相邻，d（v）<11，且设2－点u 相邻的另一个点为w，由引理1 可得G－{u}+{vw}是简单图,且是13－完备可染的，现在把vw 的色染给uw，考察边uv，至多关联11 个元素，故可染边uv，再考察点u，关联6 个元素，故可染，最后考察面uvw，至多关联8 个元素，故可染，即G 是13－完备可染的，所以矛盾，即2－点只能与11－点相邻。

引理3 设uv 是G 的一条边，d（u）=3,则d（v）>9。

证明：设u相邻的另一个点为w,由引理1可得G－{uv}+{vw}是简单图,且是13－完备可染的，现在先删去u 的颜色,把vw 的色染给uw，则依次可染上uv，u。

引理4 若G 内不含有一个5-面关联2 个3-点,且这两个3-点相邻。

证明：假设存在一个5-面f，关联2个3-点u,v,，由引理1可得G－{uv}是简单图,且是13－完备可染的。现在对G 进行染色，先删除5-面f，点u，v 的颜色，考察f 至多关联12 个颜色，故可染，再考察点u，点v，边uv 分别至多关联9 个颜色，故全部可染，则G是13－完备可染的，所以矛盾，即G 内不含有一个5-面关联2 个3-点,且这两个3-点相邻。

二、定理1 的证明

权转移规则：

R1:11－点转移1 给相邻的2－点。

以下考察顶点的新权：

2－点v：由引理2 及R1，w′(v)＝－2＋2＝0；3－点v：w′(v)＝w(v)＝0

v－点：4 ≤d（v）≤5，w(v)>0；

其次考察面的新权：