首页> 中文学位 >曲面可嵌图的在线列表染色
【6h】

曲面可嵌图的在线列表染色

代理获取

目录

摘要

1 绪论

1.1 基本概念

1.1.1 曲面可嵌图

1.1.2 在线列表染色

1.1.3 d-defective在线列表染色

1.2 研究概况

1.3 本文的主要结果

2 局部平面图的在线列表染色

2.1 局部平面图的结构研究

2.2 5-连通的局部平面图

2.2.1 5-连通的局部平面图结构性质

2.2.2 在线列表染色的游戏策略

2.3 局部平面图的在线选择数

3 局部平面图的非正常在线列表染色

3.1 平面图的defective在线列表染色

3.2 基本5-连通的局部平面图的defective在线列表染色

3.2.1 基本5-连通的局部平面图的结构性质

3.2.2 Defective在线列表染色游戏的策略

3.3 局部平面图的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-defective2-可染的,每个平面图是2-defective3-可染的。Eaton和Hull还有Skrekovski分别扩展了上述的结果,证明了每个外平面图是2-defective2-可选的,每个平面图是2-defective3-可选的。Cushing和Kierstead之后证明了每个平面图是1-defective4-可选的。本文中,我们证明了对于任意给定的曲面S,存在一个常数w使得每一个边宽至少为w的S-可嵌图均为2-defective在线4-可选的。

著录项

  • 作者

    韩铭;

  • 作者单位

    浙江师范大学;

  • 授予单位 浙江师范大学;
  • 学科 运筹学与控制论
  • 授予学位 硕士
  • 导师姓名 朱绪鼎;
  • 年度 2015
  • 页码
  • 总页数
  • 原文格式 PDF
  • 正文语种 中文
  • 中图分类 图论;
  • 关键词

    曲面可嵌图; 在线列表染色; 在线选择数;

相似文献

  • 中文文献
  • 外文文献
  • 专利
代理获取

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号