王维凡, 桂 浩

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

0 引 言

本文所指的图均为有限的、无向的简单图.给定一个图G,分别用V(G),E(G),|G|,δ(G),Δ(G)(简记为Δ)表示G的顶点集合、边集合、阶、最小度和最大度.一个图G的顶点k-染色是指V(G)到颜色集合{1,2,…,k}的一个映射φ,使得任意2个相邻的顶点x和y满足φ(x)≠φ(y);G的色数χ(G)定义为使得G有k-染色的最小整数k;给定G的一个k-染色φ,用Vi表示染颜色i的顶点集合;如果对任一对i, j∈{1,2,…,k}有||Vi|-|Vj||≤1,那么就称φ为G的均匀染色,或者G是均匀k-可染的;图G的均匀色数定义为: χe(G)=min{k | G是均匀k-可染的}.

显然, χe(G)≥χ(G),且不等式可以严格成立.1973年,Meyer[1]引进了图的均匀染色的概念,并提出以下猜想:

猜想1若G不是完全图也不是奇圈,则χe(G)≤Δ.

1970年,Hajnal等[2]证明了对于k≥Δ+1,任意一个最大度为Δ的图G都是均匀k-可染的;文献[3]应用算法分析给出了一个新的且短的证明;1994年,文献[4]提出以下猜想：

猜想2[4]如果一个连通图G不是Km,C2m+1和K2m+1,2m+1(m≥1),那么图G是均匀Δ-可染的.

文献[4]证明了猜想2对Δ≤3的图成立;文献[5]证明了猜想2对Δ=4的图也成立.此外,猜想2还被证明对下面特殊图类成立:树[6]、 二部图[7]、外平面图[8]及Δ≥14d+1的d-退化图[9]等.这里,如果G的每一个导出子图H包含一个度至多为d的顶点,那么就称图G为d-退化的.文献[10]证明了猜想2对于Δ≥13的平面图是成立的;文献[11]将这个结果改进到Δ≥9的情形.因此,对于平面图族,仅剩下5≤Δ≤8的情形没有解决.文献[12]证明了:Δ≥7且没有4-,5-圈的平面图满足猜想2;文献[13]证明了围长大于或者等于5的平面图满足猜想2.

本文旨在改进文献[12]中的结果,将证明:每一个5≤Δ≤6且没有4-,5-圈的平面图满……