论文部分内容阅读
设G是一个图,图G的一个顶点染色是指k种颜色1,2,…,k对G的各个顶点的一个分配,且G的任意两个相邻顶点都分配到不同的颜色,令Vi记颜色为i的顶点的集合,如果图G的一个顶点染色对所有的i,j满足‖Vi|-|Vj‖≤1,那么称这一染色为图G的一个均匀k-染色,图G具有均匀k-染色的最小整数k称为G的均匀色数,记为Xe(G)。 W.Meyer[1]证明了:任意树T都存在均匀(「Δ(T)/2(?)+1)-染色。并提出了以下猜想: 猜想1:对于任意一个既不是完全图也不是奇圈的连通图G,有Xe(G)≤Δ(G)。 Hajnal和Szemerédi[2]较早地证明了:任意图G,对于任意的整数k≥Δ(G)+1,都存在均匀k-染色。Yap和Zhang[10]证明了:最大度Δ≥13的任意平面图G,对任意整数m≥Δ,都存在均匀m-染色。 Lih和Wu[6](Yap[12])证明了:如果图G是一个连通的二部图,且不是完全二部图K2m+1,2m+1,m≥0,那么G存在均匀Δ-染色。基于这一结果,Chen,Lih和Wu提出了以下猜想: 猜想2:如果图G是一个既不是完全图,奇圈又不是完全二部图K2m+1,2m+1,m≥0的连通图,那么G存在均匀Δ-染色。 Yap和Zhang在[7]中证明了最大度Δ≥3的连通的外平面图G存在均匀Δ-染色;在[9]中证明了:最大度Δ≥|G|/3+1的图G存在均匀Δ-染色。 本论文首先叙述了与均匀染色相关的一些背景知识,第二,三,四章分别详细地论述了以下结果: 1.任意一个阶为n的平面图G,如果围长g≥4,那么有e≤2n-4,且δ≤3;如果g≥ 6,那么有e≤3/2(n-2),且δ≤2。我们可以证明,如果Δ≥9和g≥4,或者Δ≥8和g≥6,那么平面图G存在均匀Δ-染色;