论文摘要
图G的全着色是同时对G的点和边进行着色,G的正常全着色是使得V（G）∪E（G）中相邻或相关联的元素均染不同颜色的全着色.G正常全着色所用颜色的最少数目称为它的全色数,记为XT（G）.若对G进行正常全着色,G中的一个大点所关联的△（G）条边需要△（G）种颜色,再加上这个大点本身所需要的颜色,故G的正常全着色至少需要△（G）+1种颜色,所以XT（G）≥△（G）+1. 1965年,Behzad在其博士论文中提出了猜想:“若G是简单图,则XT（G）≤△（G）+2”.人们称这一猜想为全着色猜想.到目前为止,仅对一些特殊的图类证明了全着色猜想是成立的. 在证明全着色猜想成立的同时,人们还在尝试给出图的全色数的准确值.给定图G,若XT（G）=△（G）+1,则称G是1-型的,记作G∈CT1;若XT（G）=△（G）+2,则称G是2-型的,记作G∈CT2.本文证明了几类联图满足全着色猜想并确定了它们全色数的准确值. 本文的第一部分介绍了一些基本的概念和关于全着色的结论.在第二部分中,证明了若G是空图Om和圈Cn的联图,则G满足全着色猜想.并且由此推出了空图和路的联图也满足全着色猜想.根据G的全色数,我们完整地给出了G的分类.在第三部分中,我们证明了非等部完全偶图和路的联图的全色数为△+1.第四部分证明的结果是:（1）非等部完全偶图Kn1,n2（n1<n2）和圈Cm的联图在m≠n1+2时,全色数为△+1;（2）若一个具有分划（X,Y）的完全偶图满足|X|或|Y|等于一个圈所含点的个数时,这个完全偶图和这个圈的联图的全色数也是△十1.
论文目录
相关论文文献
- [1].信息物理系统的偶图动态建模与分析[J]. 小型微型计算机系统 2015(09)
- [2].基于偶图匹配和禁忌搜索的排课新算法[J]. 系统工程理论与实践 2008(03)
- [3].偶图中与韧度相关的参数t′(G)[J]. 太原科技大学学报 2008(03)
- [4].2类特殊偶图完美匹配的计数[J]. 烟台大学学报(自然科学与工程版) 2013(02)
- [5].给定最大度的极大拉普拉斯谱单圈偶图[J]. 华东交通大学学报 2015(03)
- [6].2类偶图完美匹配的数目[J]. 西南大学学报(自然科学版) 2012(10)
- [7].在加权完全偶图中求2边最优匹配的算法[J]. 广西科学院学报 2009(01)
- [8].一种基于偶图匹配的多目标分解进化算法[J]. 控制与决策 2018(10)
- [9].群体计算中的偶图匹配算法[J]. 计算机应用与软件 2018(09)
- [10].不完全事务行为踪迹标记研究[J]. 小型微型计算机系统 2011(08)
- [11].偶图K_(n,n+7)-A(|A|≤3)的圈长分布唯一性(英文)[J]. 数学研究与评论 2008(04)
- [12].偶图中相互独立的4-圈和6-圈[J]. 山西大同大学学报(自然科学版) 2015(04)
- [13].几何约束问题的偶图分解法[J]. 东方企业文化 2013(11)
- [14].一类二分图的k-匹配数[J]. 数学的实践与认识 2010(03)
- [15].偶图范畴的规范描述[J]. 计算机科学 2013(07)
- [16].流程违例处理的行为及分析[J]. 计算机科学 2011(11)
- [17].带部分标记的软件行为踪迹研究[J]. 小型微型计算机系统 2013(03)
- [18].特定竞赛图中的最长圈问题[J]. 云南民族大学学报(自然科学版) 2008(01)
- [19].位置约束的访问控制模型及验证方法[J]. 计算机研究与发展 2018(08)
- [20].完全偶图的定向图[J]. 山东科学 2013(03)
- [21].基于改进齐套零件策略的车辆装配线新型物料配送调度[J]. 系统工程理论与实践 2018(07)
- [22].两类图的点可区别边染色数[J]. 山西大学学报(自然科学版) 2012(01)
- [23].偶图K_(n,n)-I的循环m-圈分解[J]. 信阳师范学院学报(自然科学版) 2010(02)
- [24].有向图边接通度的下界(英文)[J]. 山西大学学报(自然科学版) 2009(04)
- [25].关于似星树拟拉普拉斯谱的性质探讨[J]. 赤峰学院学报(自然科学版) 2015(09)
- [26].分互模式:生产—生活方式的高度融合[J]. 开放导报 2014(04)
- [27].基于Biclustering的中医药症关系分析[J]. 计算机工程 2010(11)
- [28].基于信任的网络群体异常行为发现[J]. 计算机学报 2014(01)