平面图的全可选和3-染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:wangfei871010
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
用G=(V,E)表示顶点集为V,边集为E的图,而图的面集,最大度,最小度分别用F,△,δ表示.若V∪ E中的元素能用k种颜色进行染色,使得任意两个相邻或相关联的元素染有不同的颜色,则称G是K-全可染的.图G的一个全色列表是一个颜色集合簇L,对G的每个元素x∈V ∪ E都配一个颜色集合L(x).若对每一个满足|L(x)|=k,x∈V∪ E的L,G都是L-全可染的,则称G是k-全可选的.图G的一个正常k-顶点染色是指一个映射φ:V→{1,…,k},使得对任意uv∈E(G),满足φ(u)≠φ(v).   关于图的全可选和边可选,有以下著名的猜想(List Coloring Conjecture):对任意图G,(a))xl(G)=x(G);(b)x"l(G)=x"(G).猜想主要由Vizing和Borodin等人独立提出.关于平面图的3-染色问题,最著名的是Steinberg猜想:不含4,5-圈的平面图是3-可染的.人们的一系列研究主要围绕这两个问题展开,通过多年研究人员的不断改进,现已有一定的进展.   本文在前人的工作基础上,围绕上述猜想和问题,在平面图的全可选中,主要运用Discharging方法证明了:   (1)△≥8且不含相交三角形的平面图G是(△+1)-全可选的;   (2)△≥9且不含相邻三角形的平面图G是(△+1)-全可选的.   在平面图的3-染色中,运用延拓性引理,坏圈,新好路的定义和Discharging等方法,证明了:   (3)不含带弦4至9-圈的平面图G是3-可染的.
其他文献
一个有序对G=(V,E)称为一个无向图,其中V是一个有限集合,E是V中的不同元素的无序对的集合.V中的元素叫做图G的顶点,E中的元素叫做图G的边.通常用V(G),E(G)分别表示图G的顶点
局部上同调理论最早是由Grothendieck定义的,在之后的数学研究中得到肯定并成为研究交换代数和代数几何的一个有效工具.1974年,Herzog对局部上同调理论进行推广,给出了广义局部
首先,本文介绍了数字图像修复技术的背景、意义、原理和几种典型的修复算法。其次,本文对于TV模型进行了详细的研究,由于其迭代修复顺序是从左到右,从上到下,而且在迭代修复过程中
在本文中,我们主要讨论了三个问题.首先,根据欧氏空间R3中一个凸体包含另一个凸体的充分条件,得到了关于凸体D的边界()D的平均曲率平方积分()()DH2dσ的一些下界估计;其次,根据超
改革开放以来,随着我国生态环境遭到了严重破坏,为改善生态环境状况,党的十八大将生态文明建设提升到五位一体的中国特色社会主义建总布局的高度.衡水总体上仍属于欠发达地区
利用共轭类的一些算术条件刻画有限群的结构是有限群理论研究的重要课题,许多群论学者都在这方面进行了研究,获得了大量的研究成果.本文继续围绕共轭类的算术条件对有限群结构的
纤维分离条件在TOPB范畴中占有重要的地位,(其中TOPB范畴中对象是以B为底的纤维拓扑空间,对于对象(X,p),(Y,q)之间的态射是连续映射φ:X→Y,满足p=q(φ)在TOPB范畴中的两个对
人力资源是企业的第一资源,是企业生存和发展的关键。如果忽视了人力资源,企业发展就会失去动力源泉。只有不断提高对人力资源开发的长期性、重要性和艰巨性的认识,把人力资源开
本文主要研究不完全市场情况下股指期货的定价问题,并对沪深300股指期货进行定价和实证.我国刚推出沪深300股指期货不久,国内股指期货市场还不成熟,所以探索在不完全市场下股指
设G是一个有限群,S是群G的不包含单位元1的子集.群G关于其子集S的Cayley图X=Cay(G,S)称为正规的,如果右乘变换群R(G)在Aut(X)=Aut(Cay(G,S)中正规.本文中通过对16p阶拟二面体群G=(a