论文部分内容阅读
图的染色理论在图论中具有非常重要的地位。图的均匀染色作为染色理论的一种特殊情况,在1973年就已经被提出,它被广泛地运用于生物学,电子学,工业生产及企业管理等领域,尤其在时间表,剖分,承载平衡等问题中有广泛的应用。近几年来,图的均匀染色的研究逐渐得到关注,并拓展出了许多分支,包括:均匀边染色,均匀全染色,均匀列表染色等。本研究分为四个部分: 第一章:主要对本论文中所涉及的一些基本概念和符号作一些说明,同时对本方向的研究背景和研究概况作一个综述。 第二章:主要研究了不含4-和5-圈的平面图的均匀染色.在Hajnal和Szemerédi证明了图的均匀色数小于或者等于△+1后,1994年Chen,Lih和Wu提出猜想:不为Kn,C2n+1和K2n+1,2n+1的连通图G是均匀△-可染的.Chen,Kierstead等人相继证明了这个猜想对于△≤4的图是成立的.2008年,朱俊蕾和卜月华验证了这个猜想对△≥7且不含4-和5-圈的平面图成立的.而在这章中,我们运用细致的结构分析和经典的权转移方法证明了5≤△≤6且不含4-和5-圈的平面图是均匀△-可染的.从而我们可以得到猜想对不含4-和5-圈的平面图是成立的。 第三章:主要研究了环面图的均匀染色.1998年,Zhang和Yap证明了每一个△≥13的平面图有一个均匀△-染色.2012年,Nakpraist通过取边-极小反例的方法证明了9≤△≤12的平面图是均匀△-可染的.因此每一个△≥9的平面图是均匀△-可染的.随后,它用相同的方法证明了△≥6且没有3-圈,△≥7且没有4-圈,△≥5且围长不小于5的平面图是均匀△-可染的.本章旨在将这些结果推广到环面图上.证明了△≥12的环面图,△≥7且不含4-圈的环面图,△≥9且不含5-圈的环面图是均匀△-可染。 第四章:研究了△≤3的图的均匀全染色。1994年,Fu提出猜想:每一个图G是均匀全后-可染的,k≥max{x"(G),△+2}.2002年,Wang证明了每一个△≤3的重图有一个均匀全5-染色.在这章中,我们通过数学归纳法,证明了每一个△≤3的重图是均匀全k-可染的,k≥6.从而我们验证了上面的猜想对于△≤3的重图是成立的。