不含相邻三角形平面图的4-选色问题

来源 :南京师范大学 | 被引量 : 0次 | 上传用户:tang355402
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设k为正整数,G为图.我们给G每点一个长为k的任意表,如果存在一个点着色,使得每个点都可从表中得到一种颜色,则称G为k-可选色的.该文中证明了一些不含相邻三角形的平面图是4-可选色的.(1)不含相邻三角形,并且四面和三面不相邻的平面图是4-可选色的.(2)不含相邻三角形,并且四面的距离至少为3的平面图是4-可选色的.由于直接证明(1)(2)有困难,该文中给出了两个重要引理,由这两个引理完成了该文的证明.(3)不含相邻三角形,四面和三面不相邻,并且δ≥4的平面图至少含有满足下列条件之一的圈或子图:(i)每点都为4度点的4-圈.(ii)每点都为4度点,并且恰含有一弦u<,1>u<,3>的6-圈u<,1>u<,2>…u<,5>u<,1>.(iii)G-子图.(4)不含相邻三角形,四面的距离至少为3,并且δ≥4的平面图至少含有满足下列条件之一的圈或子图:(i)每点都为4度点的4-圈.(ii)每点都为4度点,并且恰含有一弦u<,1>u<,3>的6-圈u<,1>u<,2>…u<,5>u<,1>.(iii)G-子图.(iv)u<,1>为5度点,其余都为4度点并恰含有一弦u<,1>u<,3>的圈u<,1>u<,2>…u<,k>u<,1>(k≥5).(v)v<,2>和v<,k>为5度点,其余都为4度点并恰含有两弦u<,2>v<,2>和u<,5>v<,k>的圈u<,1>u<,2>…u<,5>u<,1>v<,2>v<,3>…v<,k>u<,1>(k≥4).
其他文献
该文主要研究了图弱控制的束缚数(b(G)),图弱控制的广义束缚数(b(G)),γ-Edge-Removal-critical(γ-ER-critical)图和γ-Edge-Removal-critical(γ-ER-critical)图,并分为三
范畴中的Hopf代数概念是很早提出的.当H为Hopf代数时,考虑M(H模范畴)和M(H-余模范畴)中的Hopf代数是人们感兴趣的课题.特别地,当H=kG时,由于M中的元素为G-分次模,则M中的Hopf
该文主要讨论了B(H)中二酉算子的线性组合和闭值域算子的扰动,并把上述结果应用于框架理论;得到了一系列有关框架分解和扰动的新结果.全文分四章.第一章:给出一些基本概念以
初中语文教学对学生想象力的发展有着重要意义。本文通过对想象力重要性的描述,提出了目前初中语文教学中存在的部分问题,并从课文的阅读、文章的写作和视觉的激发三个方面对
如何提高课堂效率,实现有效课堂的教学,学生的参与在这其中有着相当大的作用。但是,我们在教学中时常会遇到这样的现象:在我们的课堂上只有少数的几个同学能积极举手发言,而
所谓同课异构,是指同一教材,同一年级的不同班级,不同教师的不同教学方法来讲授的一种教学形式,其目的是让不同教师通过不同的构思,充分展示自己的实力,彰显自己的个性,来完
自上世纪20年代以来,伪回归问题一直是国内外学者争相讨论的热点问题之一;与此同时,在经济学领域,结构变点问题也同样是经济学家关注的焦点。时下,越来越多的数据服从厚尾分布,且结
<正> 江西省广丰县检察院自1979年恢复重建以来,历届党组高度重视党风廉政建设和队伍建设,始终不渝地抓教育、抓监督、抓惩处,确保队伍不出问题,办案不出问题,连续多年被县委
理论联系实际是辨证唯物主义认识论的核心内容,也是中学物理教学的基本原则.初中阶段,物理概念的建立,物理规律的得出,都要以生活实践为基础.为了充分体现“从生活走向物理,
最优化是一门应用广泛、发展迅速的学科.尤其对于非线性优化问题寻找快速有效的算法一直是优化专家们研究的热门方向之一.最近人们提出了不少有效地算法如:共轭梯度算法和拟