平面图的非正常染色

发布时间：2017-05-15 15:28

  本文关键词：平面图的非正常染色，由笔耕文化传播整理发布。

【摘要】：本文研究的图是有限,简单,无向图.设G=(V, E)是一个图,k是一个正整数.若存在一个映射Φ:V→{1,2…,k)满足：对任意xy∈E,都有Φ(x)≠Φ(y),则称φ是G的一个k-染色,此时我们称G是k-可染的.给G的每个顶点v分配一个颜色集合L(v),则称L={L(υ)|υ∈V}是G的一个色列表.若对任意的点v∈V,都能从其相应的色列表L(v)中选取一个颜色φ(v)染给v,使得Aυυ∈E(G),有Φ(υ)≠Φ(υ),则称G是L-可染的.若G对任意一个满足|L(v)|≥k的色列表L,G都是L-可染的,则称G是k-列表可染的,也称G是k-可选择的. 设di,i∈{1,2,...,k}是k个非负整数.若能用1,2,…,k这k种颜色对图G=(V,E)的点进行染色,使得染颜色i的点组成的点导出子图G[Vi]的最大度至多为di,i∈{1,2...,k},则称G是非正常(d1,d2,…,dk)-可染的,或简称(d1,d2,…,dk)-可染的.若d1=d2=…=dk=d,则称G是d-非正常k-可染的,或称(k,d)*-可染的.设d是一个非负整数,L是G的一个色列表.若对每一个L={L(υ)|υ∈V,|L(υ)|≥k},我们都能用L(v)中的一种颜色去染v,使得染颜色i的点组成的点导出子图G[Vi]的最大度至多为d,则称G是非正常(k,d)*-可选的,或简称(k,d)*-可选的. 易知,正常染色是非正常染色的特例,非正常染色是正常染色的推广. 1976年,Steinberg提出了一个猜想：既不含4-圈又不含5-圈的可平面图是3-可染的.由于解决著名的Steinberg猜想有很大的难度,Erdos提出这样的一个问题：寻找一个常数C,使得不含4到C-圈的可平面图是3-可染的. 本论文分为四章,主要围绕以上猜想和问题展开研究,所得结论改进了现有的一些结果.第一章介绍了本论文所涉及的有关定义,并对正常染色和非正常染色的研究现状做了一个综述.第二章主要讨论既不含4-圈又不含5-圈的可平面图的非正常染色,第三章主要讨论既不含4-圈又不含6-圈的可平面图的非正常染色.第四章主要讨论不含4-圈的可平面图的非正常列表染色.
【关键词】：可平面图 非正常染色 圈 权转移
【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：O157.5
【目录】：

• 摘要3-5
• ABSTRACT5-7
• 目录7-8
• 1 绪论8-14
• 1.1 基本概念8-10
• 1.2 非正常染色的研究概况10-13
• 1.3 本文的主要结果13-14
• 2 既不含4-圈又不含5-圈的可平面图的非正常染色14-35
• 2.1 既不含4-圈又不含5-圈的可平面图是(1,1,0)-可染的14-28
• 2.2 既不含4-圈又不含5-圈的可平面图是(3,0,0)-可染的28-35
• 3 既不含4-圈又不含6-圈的可平面图的非正常染色35-46
• 3.1 既不含4-圈又不含6-圈的可平面图是(1,1,0)-可染的35-41
• 3.2 既不含4-圈又不含6-圈的可平面图是(3,0,0)-可染的41-46
• 4 不含4-圈的可平面图的非正常列表染色46-54
• 参考文献54-58
• 在学期间的研究成果及发表的论文58-59
• 致谢59-62

【共引文献】

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

1 王应前;金利刚;亢莹利;;没有4至6-圈的平面图是(1,0,0)-可染的[J];中国科学:数学;2013年11期

2 赵春红;蔡宇泽;;一类不含5-圈平面图结构的几个结论[J];沙洲职业工学院学报;2013年02期

  本文关键词：平面图的非正常染色，由笔耕文化传播整理发布。

，

本文编号：368178