论文部分内容阅读
图的染色是图论研究的重要内容.在现代计算机科学、信息科学等领域有着十分广泛的的应用,一直得到国内外同行的极大关注.本学位论文主要围绕着图的六大染色问题展开,即:无圈点列表染色、星染色、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的情况.