不含4-扇的平面图的全染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:kongjiahao
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设G=(V, E,F)表示顶点集为V,边集为E及面集为F的图.它的最大度与最小度用△与δ表示.图G的一个k-全染色是一个映射φ:V∪E→{1,…,k},使得对任意相邻或相关联的元素u和v,满足φ(u)≠φ(v).若G有一个k-全染色,则说G是k-全可染的.图G的全色数是指最小的正整数k的值.显然,全色数至少为△+1.  关于图的全染色,在20世纪60年代,Vizing和Behzad就相互独立的提出:每个(简单)图G都是(△+2)-全可染的.这就是著名的全染色猜想,简称TCC.到目前为止,只有△=6的全染色猜想尚未得到解决.对于△=6平面图的全色数,吴建良和王应前等分别证明不含3-圈或不含4-圈时,TCC成立.侯建锋等证明不含5-圈或6-圈时,TCC成立.最近,Roussel给出这样的结论:若平面图的最大度为6,并且图中的每一点都不同时包含kv-圈,kv∈{3,4,5,6,7,8},则这个平面图是8-全可染的.  对于平面图,多数情况下全色数是可以达到其下界(△+1)的.首先,Borodin等人证明了△≥11的平面图是(△+1)-全可染的;其次王维凡将前述结果改进到△=10,接着Kowalik等人又继续将结果改进到△=9.至于△≤8想要证明同样整洁的结果似乎非常困难.考虑△=8的平面图的9-全可染性,侯建锋等人证明了△≥8且无4-圈的平面图是9-全可染的.此后,无4-圈的这个附加条件不断被减弱为:无5-圈或无6-圈;无相交1-扇;无2-扇;无3-扇等.  本文在前人已有的经验基础上,主要围绕TCC,在平面图的全染色猜想中,通过研究极小反例,构建新的可约构型,运用权转移的方法证明了:  (1)若G是△=6且不含4-扇的平面图,则G是8-全可染的.  (2)若G是△=8且不含4-扇的平面图,则G是9-全可染的.  这里的4-扇是指交于一点的4个相继的3-面,类似地,k个相继的3-面称为k-扇.这两个结果改进了若干同类型的相关结果.
其他文献
在过去的十年里,计算机网络的飞速发展和计算机的广泛应用使得人们对多媒体数据的获取越来越容易,这同样使得多媒体数据的非法拷贝和传播也变得容易起来,因此版权保护问题就面临
本文主要对带有PA误差样本的部分线性模型和部分线性EV模型进行了初步的研究.针对部分线性模型Y=xβ+g(t)+e,其中(x,t)属于R x[0,1], β是未知参数,g(t)是定义在【0,1]上的未知
本文在一般Banach空间中研究了渐近伪压缩映象方程和渐近非扩张映象方程三重迭代解的逼近问题。作者的结果改进了文献[10]的主要结果,把迭代条件从一致凸的Banach空间推广到任
本文主要在随机条件下研究了几类一般时间终端的倒向随机微分方程(这里及以后简记为BSDE)Lp解的存在唯一性问题,推广了已有的一些结果.  本文第一章介绍了BSDE的理论背景和
风险价值(Value-at-Risk, VaR)是从20世纪90年代初期开始发展起来的一种金融市场风险测量的方法,其核心思想是计算由于市场价格波动导致金融资产所面临的市场风险的大小.精确
本文对一类具时滞的病毒模型进行分析,得到该模型平衡点的稳定性情况.对正平衡点,导出了存在Hopf分支的条件,并给出了时滞界限τ0,确定在适当参数条件下,τ0为Hopf分支值,接着计算
当T:D→D是严格伪压缩映射时,Osilike将Xu和Ori针对非扩张映象导出的隐迭代过程用于严格伪压缩映射并得到一系列收敛性结果。 本文试图将这些结果推广到带误差的情形。并就H