平面图的非正常着色

发布时间：2017-11-03 07:13

  本文关键词：平面图的非正常着色

  更多相关文章： 平面图 非正常着色 圈 权转移

【摘要】：设G=(V，，E)是简单平面图,c_1,c_2...,c_k是k个非负整数.若图G的顶点集V能被划分成k个子集V_1，V_2,...,V_k,使得对任意的i,1≤i≤k,导出子图G[Vi]]的最大度至多为ci,则称图G是(c_1,c_2...,c_k)-可着色的.图的着色问题的研究来源于著名的四色问题,历来是图论界的热点也是难点.我们知道确定一个平面图是否是3-可着色的是NP-完备的.1959年,Grotzsch提出了一个著名的定理每一个不含三角形的平面图是3-可着色的.因此许多学者致力于寻找一个允许存在三角形的平面图是3-可着色的充分条件.1976年,Steinberg提出猜想不含4-圈和5-圈的平面图是(0,0,0)-可着色的.Xu和Wang证明了不含4-圈和6-圈的平面图是(1,1,0)-可着色的,本文在这一结论的基础上进一步改进,我们证明任何一个3-圈和4-圈不相邻及无6-圈的平面图是(1,1,0)-可着色的.论文的组织结构如下.·第一章介绍了论文的研究背景以及本文解决的问题.·第二章介绍了本文涉及到的基本概念及符号.·第三章给出了图G的可约结构.·第四章给出了权转移规则.·第五章给出了图G的点,面最终权值的验证.
【关键词】：平面图 非正常着色 圈 权转移
【学位授予单位】：华中师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要5-6
• Abstract6-8
• 第一章 引言8-10
• 第二章 预备知识10-12
• 第三章 图G的可约结构12-19
• 第四章 权转移规则19-20
• 第五章 最终权值的验证20-25
• 参考文献25-27
• 致谢27

【相似文献】

中国期刊全文数据库 前2条

1 徐利民;图的正常着色的最大方法数[J];淮南职业技术学院学报;2002年04期

2 ;[J];;年期

中国博士学位论文全文数据库 前1条

1 马建清;图的处处非零3-流、Z_3-连通性以及着色问题的研究[D];华中师范大学;2015年

中国硕士学位论文全文数据库 前1条

1 白鹰;平面图的非正常着色[D];华中师范大学;2016年

本文编号：1135157