关于图的均匀染色

来源 :浙江师范大学 | 被引量 : 2次 | 上传用户:yixiangren1976
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论在现代信息科学、生命科学中有较强的应用.如:网络设计、计算机科学、编码理论、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的中心图的均匀色数.
其他文献
人脸识别是一个具有很高理论和应用价值的研究课题,是模式识别和计算机视觉领域的一个重要分支。特征提取是人脸识别中的关键环节,不同方法提取的特征含有不同的信息,如何将
生物数学是数学与生物学之间的交叉学科.它是利用数学方法来探讨生物学方面的问题,并对和生物学有关的数学问题及理论进行研究.生物数学的主要研究对象是生态系统.具有运动能力的
本课是网络环境下的整合课,说课形式为课后说课。内容包括:教材分析、教法阐述、学法指导、媒体介绍、教学设计、板书设计、课后反思七个方面。
保险公司在收取保费的同时也将承担支付保额的风险。有时可能会因为支付保额过高而导致破产。因此,怎样采取合理策略(比如:合理的再保险或投资策略)使公司风险达到最小或者使
P2P技术的发展不仅给个人用户带来了前所未有的便利,而且也极大地推动了网络潜能的进一步开发,但是其安全性是一个影响网络推广、应用所不容忽视的问题。因此在P2P网络中建立
本文主要研究全纯映射的高阶Schwarz—Pick估计.所涉及的映射包括复平面中单位圆盘上的、复空间中单位球上的以及复的Hilbert空间中单位球上的全纯映射.全文共分六章.  
函数逼近论是现代数学的一个重要分支.在函数逼近论中,有关正算子逼近误差的估计是一个非常有趣的研究领域.有不少学者对它进行了研究,得到了许多有价值的成果.但对有关正算
学位