论文部分内容阅读
设G=(V, E)是简单平面图,c1,c2,…,ck是k个非负整数.若图G的顶点集V能被划分成k个子集V1,V2,…,Vk,使得对任意的i,1≤i≤k,导出子图G[V2]的最大度至多为c2,则称图G是(c1,c2,…,ck)-可着色的. 图的着色问题的研究来源于著名的四色问题,历来是图论界的热点也是难点.我们知道确定一个平面图是否是3-可着色的是NP-完备的.1959年,Gr(o..)tzsch提出了一个著名的定理每一个不含三角形的平面图是3-可着色的.因此许多学者致力于寻找一个允许存在三角形的平面图是3-可着色的充分条件.1976年,Steinberg提出猜想不含4-圈和5-圈的平面图是(0,0,0)-可着色的.Xu和Wang证明了不含4-圈和6-圈的平面图是(1,1,0)-可着色的,本文在这一结论的基础上进一步改进,我们证明任何一个3-圈和4-圈不相邻及无6-圈的平面图是(1,1,0)-可着色的.论文的组织结构如下. 第一章介绍了论文的研究背景以及本文解决的问题. 第二章介绍了本文涉及到的基本概念及符号. 第三章给出了图G的可约结构. 第四章给出了权转移规则. 第五章给出了图G的点,面最终权值的验证.