平面图的限制列表染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:zhongtuo97
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
令G=(V,E)是一个图.图G的一个正常k-点染色是指k种颜色对于G的各顶点的一个分配,满足任意两个相邻顶点得到不同的颜色.如果G有一个正常k-点染色,那么称G是k-可染的.G的色数定义为最小的正整数k值,并用x(G)来表示.G的一个顶点色列表配置L是一个颜色集合簇,它指定G中每个顶点x一个颜色集合L(x).如果G有一个正常的顶点染色π,使得对每个顶点x∈V,都有π(x)∈L(x),那么称G为L-可染的或称π是G的一个L-染色.假若对每一个满足|L(x)|≥k的列表配置L,G都是L-可染的,那么称G是k-列表可染的,或称k-可选的.G的选择数定义为使得G是k-可选的最小的正整数k值.  在列表染色定义的基础上,Kratochvíl,Tuza和Voigt于1998年首次提出了限制列表染色的概念.如果对于任意相邻顶点u和v均满足|L(u)∩L(v)|≤d而且G是k-可选的,那么说G是(k,d)-可选的.著名的Thomassen定理说明了平面图是(5,5)-可选的.Kratochvíl,Tuza和Voigt证明了平面图是(4,1)-可选的.之后Voigt构造了一类非(4,3)-可选的平面图.目前平面图的(4,2)-可选性仍未得到完全证实.  由于平面图的3-可选性一直是图染色问题的热点与焦点,近年来,平面图的(3,1)-可选性问题引起了研究者的极大关注.本学位论文共分为三章,主要围绕平面图的(3,1)-可选性问题展开研究,所得的结论改进了现有的一些结果.  在第一章中,先给出本文所用到的基本概念,再简述相关领域的研究现状并呈现本文的主要结果.  在第二章和第三章中,摒弃了传统的权转移方法,运用经典的Thomassen列表色延拓的方法分别证明了以下两个结果:  (1)若平面图G既不包含5-圈也不包含正常相邻的4-圈,则G是(3,1)-可选的.  (2)若平面图G既不包含6-圈也不包含相邻的4-圈和5-圈,则G是(3,1)-可选的.
其他文献
随着世界的全球化,国际之间的交流变得越来越频繁,由于英语是世界上最流行的一门语言,作为一名中国学生,尽管英语不是母语,但为了以后更好的发展,学习英语是必不可少,而要想
设G是含有n≥2个顶点的连通图,正整数k≥1.假设火在图G的某个顶点v处开始燃烧,消防员选择k个未燃烧的顶点进行防护,消防员和火在图G上依次交替移动.一旦某个顶点被消防员防护下
自上世纪中叶以来,对力学与电学中非线性振动问题的研究引起了学术界的极大兴趣,从而形成了动力系统的一个重要研究领域.目前,由常微分方程导出的动力系统混沌行为已经研究得
在本文中我们主要讨论了一类特殊的代数--表代数,它有一组特定的基。特别地,当一个表代数的基可以构成群时,我们称之为群表代数.显然,这类表代数的基的性质就是群的性质.而对于一
双线性时间序列模型是一类非线性时间序列,因为双线性项的存在,使得研究问题很复杂。在对该模型的研究中,参数估计和检验是重要的研究内容。本文对一类双线性时间序列模型进行了
格值逻辑将多值逻辑的链型真值域拓广到较一般的格上.它既能处理全序信息,又能处理不可比信息,从而更有效地刻画人脑在不确定性环境中的推理、判断和决策。对真值不完全可比较
本文分别研究全分和按比例分下的复合泊松模型。这个模型满足Cossetteet.al(2010)中涉及的F-G-M copula。我们分别得到两种分红策略下的G-S函数和期望折现分红的积分微分方程
刘嘉:  留法七年的北京人,现居上海,服装设计师、时装专栏作家、时尚达人、讲师。曾获得首届“魔法天裁全国服装设计大赛”冠军。曾担任法国时装高校讲师,个人设计钟爱法式浪漫优雅与玩味主义混搭,最擅长色彩搭配、材质拼接和搞怪图案,将趋势流行元素与实际穿着场合巧妙搭配,讲解分析。  白富美  现在对于女人最高大上的形容就是白富美。百度百科“白富美”,科属网络语言,意指皮肤白皙、家境良好、相貌出众,常用来形
Dilworth与Crawley1973年提出能否去掉上半模格条件来刻画元素的不可约完全交既分解,以及能否去掉强原子格的条件刻画紧生成格结构的问题,本文首先证明了每个元有上覆盖的紧生
随着互联网的应用越来越广泛,网络直播也变得越来越热门.网络直播发展迅速,但是相关的问题也随之暴露出来,碰触法律底线的现象不时发生.本文立足于网络直播中涉及的违法现象,