论文部分内容阅读
令图G=(V(G),E(G)).定义图G的一个k-着色:存在一个映射ψ:V(G)→{1,2,…,k}使得对每一个i,1≤i≤k,G[Vi]是无边集(这里G[Vi]表示颜色为i的点导出子图).称图G是k-可着色的,如果图G的一个k-着色存在;定义图G的一个(c1,c2,…ck)-着色:存在一个映射ψ:V(G)→{1,2,…,k},使得对每一个i,1≤i≤k,G[Vi]的最大度不超过ci.称图G是(c1,c2,…ck)-可着色的如果它的一个(c1,c2,…ck)-着色存在. 近几十年来,很多学者都很关注有关四色问题的研究.1977年,Appel和Haken在计算机的帮助下用计算的方法证明了该问题.但是,始终没有纯数学分析的证明方法,为了寻找一种纯数学分析的方法来解决该问题,很多专家学者开始对可平面图的三色问题进行深入研究.2003年,Borodin和Raspaud猜想每一个不含相邻三角形和5-圈的可平面图是3-可着色的.本文证明了每一个不含相邻三角形和5-圈的可平面图是(2,0,0)-可着色的. 第一章系统介绍了本文的研究背景、研究意义以及本文要解决的问题. 第二章详细介绍了本文所涉及到的基本概念及符号. 第三章给出了图G的一些可约结构及其相关证明. 第四章给出了一种权转移规则,并验证了经过这样的权转移之后图G的点、面的最终权值. 第五章总结全文并做出展望.