若干图的边染色和全染色

发布时间：2017-07-17 11:09

  本文关键词：若干图的边染色和全染色

  更多相关文章： 边染色 全染色 平面图 广义Mycielski图

【摘要】：图G的κ-边染色就是从边集合E(G)到颜色集合{1,2,…,κ}的一个映射,使得相邻的边得到不同的颜色.图G的边色数χ'(G)就是最小的κ,使得图G有一个正常k-边染色.图G的κ-全染色就是从点边集合V(G)u E(G)到颜色集合{1,2,…,κ}的一个映射,使得相邻的边得到不同的颜色,相邻的点得到不同的颜色,关联的点和边得到不同的颜色.图G的全色数χ'(G)就是最小的κ,使得图G有一个κ-全染色.本文研究了若干图的边染色和全染色问题,包括广义Mycielski图、3-正则图、1-平面图、平面图和奇图,主要围绕平面图边染色猜想,列表边染色猜想,全染色猜想和唯一最大度点全染色猜想,力求能给这些猜想提供更有力的证据.本学位论文共分三章.在第一章中,我们首先给出本文所需要的基本概念,然后介绍若干图的边染色和全染色的研究现状,最后呈现本文的主要结果.在第二章中,我们研究若干图的边染色.(1)刻画了广义Mycielski图的边色数;(2)考虑平面图的分数边色数,并且证明了3-正则图是(7,2)-边可染的,推进了Fulkerson猜想和Mohar猜想;(3)研究最大度点导出子图条件下的1-平面图和平面图的边染色和列表边染色问题.在第三章中,我们研究若干图的全染色.(1)证明了广义Mycielski图满足全染色猜想,并且给出类型1的若干充分条件；(2)研究最大度点导出子图条件下的1-平面图和平面图的全染色和列表全染色问题；(3)证明了奇图K(2κ+1,κ)满足全染色猜想.
【关键词】：边染色 全染色 平面图 广义Mycielski图
【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要3-4
• Abstract4-8
• 第一章 绪论8-14
• 1.1 基本概念8-9
• 1.2 边染色研究概况9-11
• 1.3 全染色研究概况11-12
• 1.4 本文主要结果12-14
• 第二章 若干图的边染色14-32
• 2.1 广义Mycileski图的边色数14-17
• 2.2 平面图和3-正则图的分数边色数17-27
• 2.2.1 平面图的分数边色数17-21
• 2.2.2 3-正则图的分数边色数21-27
• 2.3 稀疏最大度点的图的边色数和边选择数27-32
• 2.3.1 1-平面图的边色数27-28
• 2.3.2 平面图的边选择数28-32
• 第三章 若干图的全染色32-44
• 3.1 广义Mycielski图的全色数32-36
• 3.2 稀疏最大度点的图的全色数和全选择数36-41
• 3.2.1 1-平面图的全色数36-37
• 3.2.2 平面图的全选择数37-41
• 3.3 奇图的全色数41-44
• 参考文献44-48
• 攻读学位期间取得的研究成果48-50
• 致谢50-54
• 学位论文诚信承诺书54

【相似文献】

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

1 王淑栋,庞善臣;系列平行图的边色数[J];山东科技大学学报(自然科学版);2002年02期

2 牟海波;串图的边色数[J];兰州铁道学院学报;2003年03期

3 田双亮;若干n重积图的点可区别边色数[J];西北民族大学学报(自然科学版);2005年02期

4 尹志刚;费旭云;李晓彪;何建新;;关于图的圆边色数几个重要定理[J];高师理科学刊;2011年04期

5 王艳丽;苗连英;;图的集合边色数[J];山东大学学报(理学版);2012年06期

6 贾振声;何满年;张忠辅;;关于图的3—边色数[J];太原重型机械学院学报;1992年01期

7 卓新建;边色数为Δ的一个充分条件[J];曲阜师范大学学报(自然科学版);1995年04期

8 刘二根;广义图K(5,n)的边色数[J];华东交通大学学报;1997年02期

9 田双亮,张忠辅;积图邻强边色数的注记[J];兰州交通大学学报;2005年03期

10 瞿晓鸿;;一个特殊图形的边色数[J];昆明理工大学学报(理工版);2006年02期

中国重要会议论文全文数据库 前4条

1 刘华;赵鹏;马明;冶建华;张忠辅;;图S_m*F_n的邻点可区别的边色数[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

2 包世堂;;关于C_m懔C_n的边色数[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

3 赵传成;;关于C_m·S_n和C_mΔSn的边色数[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

4 马刚;;S_m∨F_n的全色数和点可区别边色数[A];中国运筹学会第九届学术交流会论文集[C];2008年

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

1 高毓平;图的边染色及一些有限制条件的染色[D];山东大学;2016年

2 贺丹;图的距离边标号及其相关问题[D];东南大学;2015年

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

1 郭振香;对具有大围长可平面图强边色数的研究[D];河南大学;2015年

2 杨灿权;若干图的边染色和全染色[D];浙江师范大学;2015年

3 杨海珍;一些图的圆边色数[D];首都师范大学;2008年

4 章文超;图的贪婪博弈边色数和游戏边色数[D];浙江师范大学;2014年

5 毛新叶;图的点可区别边染色的一些结果[D];西北师范大学;2009年

6 刘利群;图的D（2）-点可区别及点可区别正常边染色[D];西北师范大学;2007年

7 田京京;图的D（β）-点可区别边染色及其概率方法[D];西北师范大学;2007年

8 杨玉红;若干图类的星边染色[D];西北师范大学;2009年

9 邓凯;图的星边染色[D];西北师范大学;2007年

10 薄朝升;星着色和强边着色的研究[D];重庆大学;2011年

，

本文编号：553290