平面图的3列表染色及FM分解

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:shize
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图G的一个正常k染色是指一个映射φ:V→{1,…,K),使得对任意uv∈E(G),有φ(u)≠φ(v).若图G有一个正常k染色,则称图G是k可染的.   设G=(V,E),给G的每个顶点v∈V(G)分配一个可用色集合L(v)(不同的点可以分配相同或不同的可用色集合),则得到G的一张色列表L={L(v)|v∈V}.若对任意的v∈V,都能从相对应的色列表L(v)中选取一个颜色染给v,使得G有一个正常染色,则称G是L可染的.若对G的任意一张满足|L(v)}≥k((V)∈V)的色列表L,G都是L可染的,则称G是k列表可染的.   1996年,Gutner证明确定一个平面图是3列表可染,或4列表可染的问题是NP困难的.因此,寻找平面图是3或4列表可染的充分条件成为图的染色理论中的一个重要研究课题.   2006年,Montassier等人证明了不含4,5,6圈且三角形的距离至少为3的平面图是3列表可染的;2008年,Montassier等人证明了6-圈的距离至少为3的平面图是3列表可染的.本文在前人的工作基础上,综合运用Discharge和结构分析等方法,得到了一个更好的结果:   (1)每一个不含相交I圈与j圈,4≤I≤j≤6,且三角形与5-圈的距离至少为3的平面图是3列表可染的.   2005年,Lam等人证明了没有3,5,6圈的平面图是3列表可染的.2008年,Zhang等人证明了没有5,6,7圈且三角形距离至少为3的平面图和没有5,6,8圈且三角形距离至少为2的平面图都是3列表可染的;2008年,Montassier等人证明了7-圈的距离至少为2的平面图是3列表可染的.本文在前人的工作基础上,综合运用Discharge和结构分析等方法,得到了一个更好的结果:   (2)相邻两圈的长度之和至少为11且三角形距离至少为2的平面图是3列表可染的.   1995年,Thomassen证明了围长为5的平面图是3列表可染的;2009年,Li证明了没有3圈且4圈不与4,5圈相交的平面图是3列表可染的.本文在前人的工作基础上,综合运用色延拓和归纳等方法,得到了一个更好的结果:   (3)没有三角形且4圈不与4,5圈相邻的平面图是3列表可染的.   图G的分解是指把图G分解成图G的一系列子图且图G的每条边出现且只出现在一个子图内.图G的FM分解是指把图G分解成两个子图,一个为森林(Forest),另一个为匹配(Matching).   2002年,He等人证明了围长至少为11的平面图可以分解成一个森林和一个匹配.2004年,Kleitman等人证明了围长至少为10的平面图可以分解成一个森林和一个匹配.2008年,Borodin等人证明了围长至少为9的平面图可以分解成一个森林和一个匹配,并在文中提出对于围长至少为8的平面图是否可以分解成一个森林和一个匹配仍旧是一个公开且有趣的问题.   围绕上述问题,本文在前人研究的基础上,运用粘点和Discharge等方法,继续研究平面图的FM分解问题,证明了:   (4)围长至少为8的平面图可以分解成一个森林和一个匹配.
其他文献
文章针对三种主要量子纠错码的多量子比特纯态的纠缠进行了研究.在量子计算和量子信息领域,量子纠缠不仅是一种重要的物理资源而且也是量子理论的最主要特征,已经成为重要的研
非线性发展方程解的爆破理论是偏微分方程的重要内容。在本文第二章中,我们首先研究了一类带有反平方势函数的半线性热方程:ut=△u-V(x)u+a(x)Up在非局部非线性边界条件:u=∫ΩK
1960年,Erd(o)s和Moser提出在一般n阶无向图G中求极大独立集个数的最大值,以及何时达到最大值的问题.Erd(o)s解决了这个问题,随后,Moon和Moser也独立的给出了这个问题的相关
学位
本文围绕常微分算子领域中的不同微分算子谱之间的关系、数值计算以及具有内部不连续点的微分算子的谱分析等三个方面开展研究工作. 不同微分算子谱之间的关系是Sturm-Lio