运用权转移方法研究图的若干染色问题

来源 :苏州大学 | 被引量 : 2次 | 上传用户:dengliang109
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的染色是图论研究的重要内容.在现代计算机科学、信息科学等领域有着十分广泛的的应用,一直得到国内外同行的极大关注.本学位论文主要围绕着图的六大染色问题展开,即:无圈点列表染色、星染色、Injective染色、点荫度、分数染色以及边面全染色.除了分析探讨图的自身结构之外,我们主要运用著名的Discharging方法来研究平面图的染色问题.   在第一章,我们给出本文所用到的基本概念,简述了相关领域的研究现状,并给出本文的主要结果.   在第二章,我们着重研究平面图的无圈点列表染色问题.此类问题最早(2002)是由Borodin,Fon-Der Flaass,Kostochka,Raspaud和Sopena引入和研究的.他们证明了每个平面图是无圈7-点列表可染的,并且提出了极具挑战性的猜想:每个平面图是无圈5-点列表可染的.我们在第二章中给出目前最接近此猜想的结果,并且还得到了平面图无圈3-点列表染色以及4-点列表染色的充分条件.   在第三章,我们将集中精力研究Subcubic图的星色数.利用对Subcubic图的结构分析,我们证明了:每个Subcubic图是6-星-可染的.需要说明的是:这个结果是最好可能的,因为Fertin,Raspaud和Reed已经给出了Wagner图不是5-星-可染的结论.   在第四章,我们将主要探讨K4-minor-free图的Injective色数问题.图G的点染色被称作是Injective的,如果任意点u的邻点颜色互不相同.我们将证明:每个非空的K4-minor-free图G的Injective色数最多是[3/2△(G)].此结果,当△(G)为偶数时,是最好可能的,因为存在一个非空的K4-minor-free图H(△(H)为偶数)的Injective色数恰好为[3/2△(H)].另外,我们还给出了一般平面图的Injective色数上界.   一个非平凡图G的点荫度va(G)是一个最小图顶点划分数使得每一个划分集的导出子图是一个森林.近年来,图的点荫度问题的研究成为图论的一个焦点.在第五章,我们将完全解决Raspaud和Wang提出的猜想:每个不包含相交三角形的平面图的点荫度最多是2.   在第六章,我们将通过研究Sparse图与Petersen图的同构关系来讨论Sparse图的分数染色.证明了每个无3-圈且最大平均度小于5/2的图是(5,2)-可染色的.我们将通过反例说明:条件“无3-圈”和“最大平均度小于5/2”都是必不司少的.   最后,在第七章,我们讨论了平面图的边面全染色问题.2001年,Sanders和Zhao提出了极具挑战性的猜想:每个平面图G是(△(G)+2)-边面全染色的并且先后解决了△≥7和△≤3的情况.迄今为止,△∈{4,5,6)的情形仍然是开放的.作为本学位论文的亮点之一,我们彻底解决了△(G)=6的情况.
其他文献
近些年来,空间信息技术领域的高速发展使我们进入信息变革的时代。空间数据通过传感器或者其他数据收集设备源源不断地收集起来,并呈指数级增长。为了能够有效管理数据,人们
曾经一个很偶然的机会,我有幸在宜昌徐爱国的工作室见到他的作品,当时就给我留下了深刻的印象,因为在远离艺术喧嚣的小城宜昌,徐爱国仍旧保持了对艺术的饱满热情,这种情感朴
删位/捅位纠错码可以用来纠正码字传送过程中因码元的删除或插入而引起的差错.完备的删位纠错码是一类码字长度一致的删位/捅位纠错码,已有不少相关的研究成果.作为完备删位纠
果树一旦步入中老龄,多现枝条萎缩、干枯,树体老化等现象,果品无论质量还是数量,都呈下降趋势,开始出现“大小年”这样极度困扰果农的难题。而在沂源县南麻镇上高村“‘垂柳
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
本文是在特定的条件下,利用变分法证明了Yang-Mills-Chern-Simons模型中局部涡旋解的存在性,同时讨论了α(τ),h(τ)和q(τ)的性质,并给出了h(τ),α(τ)和q(τ)的渐近估计.    
相补问题理论与变分不等式理论紧密相关。   相补问题理论及应用的研究始于20世纪60年代Lemke,Cottle,和Damtizig等人的工作。这一理论具有广泛的实际背景。在一定的条件
SFL算法是一种经典的进化算法,相对于其它进化算法,它收敛快速等诸多优点。据此,本文提出一种基于SFL算法的实例选择算法(SFLSS:Shuffled Frog Leaping Sample Selection)。
随着人们对环境保护意识的逐渐加强,上海纺机展也积极响应行业发展需求,致力于为观众呈现降低能源损耗的纺织技术,并与不同领域的专家合作,将最前沿的行业发展信息带给现场观
随着时代的不断发展,创新思维能力成为对人才的重要要求.因此,在初中数学教学中教师要从教学特点上出发,采取有针对性的措施,培养好学生的创新思维能力,以此来满足学生的学习