平面图的非正常着色

来源 :华中师范大学 | 被引量 : 0次 | 上传用户:fly_bird2
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设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的点,面最终权值的验证.
其他文献
设N, t,k,gi(i=1,2,…,k)为正整数,其中2≤t≤k.Gi是一个大小为gi的集合.一个混合覆盖阵,MCA(N;t,k,g1g2…gk),定义为一个N×尼阵列,第i列上的所有元素取自集合Gi;且对任意有序序
本文研究了在三维空间中,完全Navier-Stokes-Maxwell系统经典解的爆破准则,即,当速度u满足Scrrin条件,密度ρ的L∞tL∞x范数和电场的二阶导数▽2E的L3tL2x范数有界时,我们可以得到
中立型时滞系统是一种特殊的时滞系统,它能更深刻、更精确地反映事物变化的规律,揭示事物的本质,因此关于中立型时滞系统的稳定性研究十分必要,并已得到了国内外诸多学者的重
单位球面中的极小超曲面是子流形几何中的重要研究对象,而陈省身猜想是关于它的一个重要问题.1968年,陈省身猜想提出n+1维单位球面中具有常数量曲率的闭极小子流形的第二基本形