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