曲面可嵌图的在线列表染色
发布时间：2017-08-17 18:26
本文关键词：曲面可嵌图的在线列表染色
更多相关文章： 在线选择数 在线列表染色 边宽 曲面 局部平面图 d-defective在线列表染色
【摘要】：本文探究曲面可嵌图的在线选择数与非正常的在线选择数。图的在线选择数是选择数的在线形式,并且它总是不小于其选择数。类似的,d-defective在线选择数是d-defective选择数的在线形式,并且它总是不小于其d-defective选择数。在本文中,我们将选择数和d-defective选择数的一些著名的结果推广到了在线选择数和d-defective在线选择数。对于嵌入在曲面S上的图G,其边宽ew(G)为G的最短的不可缩圈的长度,其中不可缩圈是指其嵌入为S上的一条不可缩的闭Jordan曲线的圈。在1993年,Thomassen证明了对于任意给定的曲面S,存在一个常数w使得每一个边宽至少为w的S-可嵌图均可5染色。DeVos, Kawarabayashi和Mohar在2008年证明了对于任意给定的曲面S,存在一个常数w使得每一个边宽至少为w的S-可嵌图均为5-可选的。本文对上述的结论进行了扩展,证明了对于任意给定的曲面S,存在一个常数w使得每一个边宽至少为w的S-可嵌图均为在线5-可选的。图G的d-defective染色是指G的一个顶点染色,满足每个色集的导出子图的最大度至多为d。在1986年,Cowen, Cowen和Woodall证明了每个外平面图是2-defective 2-可染的,每个平面图是2-defective 3-可染的。Eaton和Hull还有Skrekovski分别扩展了上述的结果,证明了每个外平面图是2-defective 2-可选的,每个平面图是2-defective 3-可选的。Cushing和Kierstead之后证明了每个平面图是1-defective 4-可选的。本文中,我们证明了对于任意给定的曲面S,存在一个常数w使得每一个边宽至少为w的S-可嵌图均为2-defective在线4-可选的。
【关键词】：在线选择数 在线列表染色 边宽 曲面 局部平面图 d-defective在线列表染色
【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：
- 摘要3-5
- ABSTRACT5-9
- 1 绪论9-17
- 1.1 基本概念9-13
- 1.1.1 曲面可嵌图9-10
- 1.1.2 在线列表染色10-12
- 1.1.3 d-defective在线列表染色12-13
- 1.2 研究概况13-16
- 1.3 本文的主要结果16-17
- 2 局部平面图的在线列表染色17-40
- 2.1 局部平面图的结构研究17-24
- 2.2 5-连通的局部平面图24-37
- 2.2.1 5-连通的局部平面图结构性质24-30
- 2.2.2 在线列表染色的游戏策略30-37
- 2.3 局部平面图的在线选择数37-40
- 3 局部平面图的非正常在线列表染色40-68
- 3.1 平面图的defective在线列表染色40-57
- 3.2 基本5-连通的局部平面图的defective在线列表染色57-65
- 3.2.1 基本5-连通的局部平面图的结构性质57-60
- 3.2.2 Defective在线列表染色游戏的策略60-65
- 3.3 局部平面图的defective在线选择数65-68
- 参考文献68-70
- 在学期间的研究成果及发表的论文70-71
- 致谢71-73
- 浙江师范大学学位论文诚信承诺书73
【相似文献】
中国期刊全文数据库 前1条
1 邓默;任韩;董倩;;局部大边宽嵌入图的面圈和C-桥的结构(英文)[J];数学季刊;2008年04期
中国硕士学位论文全文数据库 前2条
1 韩铭;曲面可嵌图的在线列表染色[D];浙江师范大学;2015年
2 聂美玲;筑W被⺈弊枇Φ牟馐苑治鲇胫⺈敝柿科兰踇D];东北农业大学;2014年
，本文编号：690440
本文链接：https://www.wllwen.com/kejilunwen/yysx/690440.html
