论文部分内容阅读
本文研究的图是有限,简单,无向图.设G=(V,E)是一个图,k是一个正整数.若存在一个映射φ:V→{1,2,…,k}满足:对任意xy∈E,都有φ(x)≠φ(y),则称φ是G的一个k-染色,此时我们称G是k-可染的.给G的每个顶点v分配一个颜色集合L(v),则称L={L(v)|v∈V}是G的一个色列表.若对任意的点v∈V,都能从其相应的色列表L(v)中选取一个颜色φ(v)染给v,使得(V)uv∈E(G),有φ(u)≠φ(v),则称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)|v∈V|L(v)|≥k},我们都能用L(v)中的一种颜色去染v,使得染颜色i的点组成的点导出子图G[Vi]的最大度至多为d,则称G是非正常(k,d)*-可选的,或简称(k,d)*-可选的. 易知,正常染色是非正常染色的特例,非正常染色是正常染色的推广. 1976年,Steinberg提出了一个猜想:既不含4-圈又不含5-圈的可平面图是3-可染的.由于解决著名的Steinberg猜想有很大的难度,Erd(o)s提出这样的一个问题:寻找一个常数C,使得不含4到C-圈的可平面图是3-可染的. 本论文分为四章,主要围绕以上猜想和问题展开研究,所得结论改进了现有的一些结果.第一章介绍了本论文所涉及的有关定义,并对正常染色和非正常染色的研究现状做了一个综述.第二章主要讨论既不含4-圈又不含5-圈的可平面图的非正常染色,第三章主要讨论既不含4-圈又不含6-圈的可平面图的非正常染色.第四章主要讨论不舍4-圈的可平面图的非正常列表染色.