外可平面图的非正常多重染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:cmccetehi
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设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)-可选的.  第一章主要介绍了本论文所涉及一些定义,并且介绍了多重染色及非正常染色的发展历程和研究现状.第二章讨论一般意义下的列表配置下的外可平面图的非正常多重染色.第三章讨论了在对列表进行限制的情况下外可平面图的非正常多重染色.
其他文献
众所周知,微分系统定性理论的一个主要问题是研究平面多项式微分系统的极限环问题,对于一般的平面多项式微分系统从线性中心的周期环域分支出极限环的最大个数问题已经有了大量
本论文先引入了变指数向量值Bochner-Letbesgtle和Bochne-Sobolev空间,然后得到了这些新空间的一些性质,如完备性,共轭空间,自反性,一致凸性,一致光滑性.这些结果推广了相应变指数
半群的代数理论是近些年来科学研究的热点之一.由于半群理论在应用数学、计算机科学、密码编码学等领域中都有广泛的应用,所以发展非常迅速.本课题受前人研究的wpp半群及其密
学位