论文部分内容阅读
图染色是图论研究中的重要问题和热点之一,有重要的理论价值和应用背景.1976年,Stahl在图的顶点染色的基础上提出了k-重顶点染色概念.G=(V,E)表示一个顶点集为V,边集为E的有限简单无向图.若存在映射φ:V(G)→Zk(n)(Zk(n)是由{1,2,…,n}的所有k-元子集构成的集合),满足:()uv∈E(G),有φ(u)∩φ(u)=(),则称φ是图G的一个k-重n-顶点染色.若图G有一个k-重n-顶点染色,就称G是k-重n-顶点可染的.称xk(G)=min{n:G是k=重n-顶点可染的}为G的k-重色数.当k=1,x1(G)就是正常的点色数,即x1(G)=x(G).有关这方面的研究成果不是很多,有许多问题还有待解决.本论文主要讨论了平面图的k-重染色问题.
本学位论文由四章组成.第一章是对本学位论文涉及到的问题背景,定义及进展等各方面给出一个综述.
在之后的两章中,我们主要研究了平面图的k-重染色,通过探讨平面图的一系列特殊结构.利用权转移的方法证明了如下结果:
(1)奇围长至少为19的平面图G是3-重7-可染的；
(2)奇围长至少为11的平面图G是2-重5-可染的;
(3)奇围长至少为13的平面图G是4-重10-可染的.
(4)奇围长至少为21的平面图G是6-重14-可染的.
最后一章提出了关于平面图k-重染色的若干问题.