学位论文 > 优秀研究生学位论文题录展示

最大度大于等于7的平面图全染色

作　者: 陶鑫
导　师: 王应前
学　校: 浙江师范大学
专　业: 运筹学与控制论
关键词: 平面图全染色最大度带弦5-圈 6-圈相交三角形权转移
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 20次
引　用: 0次
阅　读: 论文下载

内容摘要

图的全染色问题的研究来源于著名的四色问题.设V,E,△和δ分别表示图G的顶点集,边集,最大度和最小度.若能用k种颜色对G进行染色,使得任意2个相邻或相关联的元素(元素指的是顶点或边)染有不同的颜色,则称G是k-全可染的.给每一个图进行全染色至少要用△+1个颜色Vizing和Behzad分别提出了著名的全染色猜想(Total Coloring Conjecture),简称为TCC：任何简单图G都是(△+2)-全可染的.但是关于这一猜想即使对于平面图还剩下△=6未被解决.近年,随着研究的深入,国内外学者发现很多平面图类的全色数还能取到相应的下界(Δ+1). Borodin等人证明了△≥11的平面图是(△+1)-全可染的；王唯凡证明了△=10的平面图是(△+1)-全可染的；Kowalik等人证明了△=9的平面图是(△+1)-全可染的.由于K4不是4-全可染的,于是王应前提出了平面图的全染色猜想(简称为PTCC):任何简单平面图G都是(△+1)-全可染的,其中△≥4.侯建峰,沈岚等人分别研究了△≥8的一些平面图类是(△+1)-全可染的.在此基础上,本学位论文主要运用权转移方法,并结合深度挖掘可约构型的方法研究了△≥7的平面图类关于PTCC成立.

全文目录

摘要  3-4
ABSTRACT  4-5
目录  5-7
1 绪论  7-11
  1.1 基本概念  7-8
  1.2 全染色问题的研究概况  8-10
  1.3 本文主要结果  10-11
2 △≥6的平面图的全染色  11-16
  2.1 △≥6且不含5-圈和6-圈的平面图的全染色  11-16
3 △≥7的平面图的全染色  16-60
  3.1 △=7且不含带弦5-圈的平面图的全染色  16-20
  3.2 权转移  20-28
  3.3 △=7且不含6-圈的平面图的全染色  28-34
  3.4 权转移  34-43
  3.5 △=7且不含相交三角形的全染色  43-53
  3.6 附加权转移  53-59
  3.7 △≥7的平面图的全染色  59-60
参考文献  60-63
攻读学位期间取得的研究成果  63-64
致谢  64-66

最大度大于等于7的平面图全染色

内容摘要

全文目录

相似论文