论文部分内容阅读
图论在现代信息科学、生命科学中有较强的应用.如:网络设计、计算机科学、编码理论、DNA的基因谱的确定和计数、工业生产和企业管理中的优化方法等都非常广泛地应用了图论及其算法.近年来国际上有四个数学大奖先后被与图论与组合论方向有关的数学家获得:Kim在1997年获Furkerson奖;Cowers在1998年获Fields奖;Lovász和Shelah分别在1999年和2001年获Wolf奖.
图的染色理论是图论研究的热点问题之一.图的均匀染色理论作为图的染色理论的一种特殊情况,在早期就已经被提出,它被广泛的应用于工业生产、企业管理和生物学等领域.尤其在研究时间表、剖分、承载平衡等问题中,均匀染色理论一直起着举足轻重的作用.但是发展至今,该理论的研究成果还不完善.近年来,随着图的列表染色研究逐渐得到关注,人们开始研究图的列表均匀染色,但所得的研究结果也不是很多.本学位论文对于某些限制条件的图的均匀染色加以研究.论文由三章组成
在第一章中,我们主要是对本论文所涉及到的问题的背景,概念以及本方向研究概况做一个综述.
在第二章中,我们主要研究了平面图的列表均匀染色.Kostochka,Pelsmaier和West三人在2003年提出了如下两个猜想:对于图G,如果k≥△(G)+1,那么G是k-均匀可选择的;最大度不小于3并且不是完全图和Km+1,2m+1的连通图G是△(G)-均匀可选择的.我们应用权转移技术,讨论了不含某些圈的平面图的结构.证明了对于不含4-圈,8-圈和9-圈的平面图G,当k≥mma{△(G),9}时,G是k-均匀可选择的,同时,G也是k-均匀可染的;对于不含4-圈,10-圈和相交5-面的平面图G,当k≥max{△(G),9}时,G是k-均匀可选择的,同时,G也是k-均匀可染的.
在第三章中,我们主要研究了蛛形图的全图和中心图的均匀色数.通过研究蛛形图的全图和中心图的性质,给出具体的独立集分解,得到了蛛形图G删去头点后有n条长为n—1的路.把图G的全图记为T(G),则G的全图的均匀色数xEq[T(G)]=n+1.把G的中心图记为C(G),也得到了这样的蛛形图G的中心图的均匀色数.