论文部分内容阅读
设f是一个映射,它给G的每个点u分配一个含有b个颜色的颜色集合f(v),那么称f为图G的一个b-重染色.给定图G的一个b-重染色f,点v相对于f的总缺憾定义为deff(v)=∑u∈N(v)|f(u)∩f(v)|.如果对于每一个点v来说,都满足deff(v)≤d,则称f是图G的一个d-缺憾b-重染色.图G的一个a-列表配置是指图G的一个每个点的颜色列表大小都至少为a的一个列表配置.假设L为图G的一个列表配置,f是图G的一个d-缺憾b-重染色.如果对于每一个顶点v,f(v)(∈)L(v),则称f是G的一个d-缺憾b-重L-染色.若对图G的任意的一个a-列表配置L,都存在图G的一个d-缺憾b-重L-染色,则称图G是d-缺憾(a,b)-可选的.图G的一个(a,∧s)-列表配置是指一个列表配置满足对任意的v∈V(G),有|L(v)|≥s,且对任意的uv∈E(G),都有|L(u)∩L(v)|≤s.类似地,若对任意的(a,∧s)-列表分配L,都存在图G的一个d-缺憾b-重L-染色,则称G是d-缺憾((a,∧s),b)-可选的.0-缺憾的b-重染色称为b-重染色.若G是0-缺憾(a,b)-可选的,则称G是(a,b)-可选的. 图的多重染色是由Stahl在1976年提出的.关于图的多重染色,在1979年,Erd(o)s,Rubin和Taylor提出了如下猜想:若图G是a-可选的,则对任意的正整数m,G也是(am,m)-可选的.该猜想是列表染色领域著名的难题,近四十年来,进展很小. 1986年,Cowen,Cowen及Woodall首次提出了非正常染色的概念,接着在1999年,Skrekovski及Eaton和Hull分别独立地将非正常染色的概念推广到了列表染色. 对于列表限制下的列表染色,1998年,Kratochvíl,Tuza及Voigt提出猜想:所有的平面图都是(4,∧2)-可选的;2001年,Skrekovski提出猜想:所有的平面图都是(3,∧1)-可选的. 本论文分为三章,我们提出Erd(o)s-Rubin-Taylor猜想的一个推广:若图G是d-缺憾a-可选的,则对任意的正整数m,G也是dm-缺憾(am,m)-可选的.本文证明了该推广了的Erd(o)s-Rubin-Taylor猜想对外可平面图成立.另外,本论文研究了在对外可平面图的列表进行一定限制下的多重非正常染色,证明了对任意的正整数b,任意外可平面图是b-缺憾((2b,∧b),b)-可选的. 第一章主要介绍了本论文所涉及一些定义,并且介绍了多重染色及非正常染色的发展历程和研究现状.第二章讨论一般意义下的列表配置下的外可平面图的非正常多重染色.第三章讨论了在对列表进行限制的情况下外可平面图的非正常多重染色.