环面图的列表染色

发布时间：2017-08-01 04:10

  本文关键词：环面图的列表染色

  更多相关文章： 环面图 正常列表染色 非正常列表染色 圈 权转移

【摘要】：本文研究的图是有限,简单,无向图.设G是一个环面图,是指图G可以嵌入到环面上,即在环面上无交叉的边.G的正常列表染色是指,G的一个顶点色表配置L是一个色集簇,L={l(V)|(?)∈V,L(v)(?)N}其中L(v)叫做v的可用色表,若映射φ：V→N满足：(1)φ(x)∈L(u),(?)∈V；(2)uv∈E(?)φ(u)≠φ(v)则称φ是G的一个L-染色.若G存在一个L-染色,则称G是L-可染的.若对每一个满足|L(v)|≥κ的色表配置L, G都是L-可染的,则称G是κ-可选的.令d是一个非负整数.G是(L,d)*-可染的,是指存在某个染色φ,使得φ(u)∈L(v)且满足G的每个顶点至多与其d个邻点染相同颜色.G的非正常列表染色,即G是(κ,d)*-可选的,是指(?)v∈V(G)分配一个色表L,|L(u)|≥k,且都存在一个(L,d)*-染色.易知,正常列表染色是非正常列表染色的特例,非正常列表染色是正常列表染色的推广图G的一个正常染色φ,若能满足G中的任意两个色的点集所导出的子图是一个星森林,则称正常染色φ是G的一个星染色.若给定图G的一个顶点色表配置L,且存在一个星染色φ使得κ(v)∈L(v),则称G是L-星-可选的.若对每一个满足|L(v)|)≥κ的色表配置L,G都是L-星-可染的,则称G是κ-星-可选的.在平面图上,正常列表染色和非正常列表染色已有不少猜想和问题已经被许多研究者所解决和证明,于是研究者开始进一步思考这些结论是否仍然适用于环面图上,后人展开了相关的研究工作并取得了一系列的成果.本论文分为四章,主要围绕环面图的列表染色展开研究,所得到的结论改进了现有的一些结果.第一章介绍了本论文所涉及的有关定义,并对正常列表染色和非正常列表染色的研究现状做了一个综述.第二章介绍了不含4-圈和i-圈(i∈{5,7,8})的环面图是(3,1)*-可选的.第三章介绍了不含4,i,j-圈((i,j)∈{(5,7),(6,8)})且三角形距离至少为3的环面图是3-可选的.第四章介绍了最大度不大于3的环面图是6-星-可选的.
【关键词】：环面图 正常列表染色 非正常列表染色 圈 权转移
【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要3-5
• ABSTRACT5-9
• 1 绪论9-16
• 1.1 基本概念9-11
• 1.2 环面列表染色的研究概况11-14
• 1.3 本文的主要结果14-16
• 2 关于环面图的非正常列表染色可染的结果16-29
• 2.1 关于(3,1)~*-可选的可约构型16-18
• 2.2 定理2.1的证明18-21
• 2.3 定2.2的证明21-24
• 2.4 定理2.3的证明24-29
• 3 关于环面图的正常列表染色可染的结果29-34
• 3.1 定理3.1的证明29-31
• 3.2 定理3.2的证明31-34
• 4 关于环面图的星列表染色的结果34-44
• 4.1 关于最大度△≤3的环面图的可约构型34-42
• 4.2 定理4的证明42-44
• 参考文献44-47
• 在学期间的研究成果及发表的论文47-48
• 致谢48-51
• 附件51

【相似文献】

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

1 邹健;胡岗;;从三维环面到混沌[J];北京师范大学学报(自然科学版);1987年02期

2 黄化宇;环面的一种特殊切面[J];赣南师范学院学报;1990年S2期

3 李炳仁,林青;C~*-代数映象环面的注记[J];科学通报;1992年19期

4 余澍祥;环面上动力系统的某些性质(英文)[J];数学研究与评论;1992年02期

5 符五久,何娟美;准周期驱动圆映射的环面分岔机制及标度关系[J];南昌大学学报(理科版);2005年02期

6 尚新春,程昌钧;环面薄膜的膨胀失稳[J];应用数学和力学;1991年06期

7 任军,章辉煌,林尊琪;掠入射光栅谱仪中的超环面镜对线状X光光源诊断的影响[J];量子电子学;1992年01期

8 陶志雄;;环面链环的多项式[J];浙江科技学院学报;2013年06期

9 邓小国;周泗忠;熊仁生;郭治理;;超环面聚焦镜压弯装置的优化设计[J];光子学报;2006年05期

10 鲍园园;雷逢春;;环面链环的辫子数(英文)[J];黑龙江大学自然科学学报;2008年02期

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

1 洪玫;姚立纲;;基于数值方法的内超环面行星齿轮齿廓离散建模[A];第十五届中国科协年会第27分会场：现代图学推动数字设计与制造论坛论文集[C];2013年

2 谢建华;丁旺才;;多自由度碰撞振动系统环面分岔与混沌研究[A];第七届全国非线性动力学学术会议和第九届全国非线性振动学术会议论文集[C];2004年

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

1 张建路;KAM环面的渐近轨道[D];南京大学;2014年

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

1 景昱波;环面图的列表染色[D];浙江师范大学;2015年

2 曹泷;叉排圆管非对称间断环面槽换热器翅片传热特性的数值研究[D];兰州交通大学;2014年

3 邓润林;牵引式全环面IVT设计方法的初步研究[D];华中科技大学;2005年

4 董操;二维环面的匹配排除[D];山西大学;2010年

5 赵雯洲;K_7在环面上的嵌入[D];华东师范大学;2012年

6 秦玉凤;环面纽结T_(3,2n)、T_(4,2n)在广义方格图中的嵌入问题和完全3-部图K_(2,5,n)的交叉数[D];东北师范大学;2014年

7 黄探霄;CP~n中具有循环调和序列的平坦极小环面[D];南昌大学;2010年

8 崔怀愈;超环面镜聚焦46.9nm软X射线激光烧蚀固体靶的实验研究[D];哈尔滨工业大学;2013年

9 孙媛媛;环面上的顶点代数层结构的实现[D];河南大学;2009年

，

本文编号：602417