共查询到10条相似文献,搜索用时 46 毫秒
1.
如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色.图G的无圈边色数表示图G的无圈边染色所需的最小颜色数.为研究平面图的无圈边色数的上界,利用差值转移方法并结合平面图的结构性质,证明了不含相交三角形的平面图的无圈边色数不超过Δ(G)+7. 相似文献
2.
赵聪俐 《数学学习与研究(教研版)》2008,(11)
设G是一个图.如果图G的顶点能够用k个颜色来染,通过这种染色使得它的每个顶点至多有d个染相同颜色的顶点和它相邻,而且这样的顶点最少为t个,那么我们称图G是(k,d,t)*-可染的.在这个新定义的基础上,本文主要给出了几种特殊图类的一些结果和它们的证明,诸如圈、完全图等.另外,通过带有限制的缺陷染色这个新定义提出了对平面图四色问题的一点新看法,对四色定理的证明可能会有所帮助. 相似文献
3.
高炜 《昆明师范高等专科学校学报》2011,(6):51-55
松弛均匀着色是松弛着色的一类特殊情况,它要求任意两个色类的顶点数之差至多为1.d-退化图是指每个导出子图都存在度至多为d的顶点的图.证明了若顶点数位rt的d-退化图G的最大度至多为△,且K≥18d,n≥17△.则G存在均匀(k-1,1)着色. 相似文献
4.
5.
设G为n阶的连通k(k≥3)圈图,λ1(G)是图G的laplacian矩阵的最大特征值.本文讨论了圈长为3的k圈图的最大特征值与其预点数及各顶点的悬挂边个数之间的关系. 相似文献
6.
王秀梅 《商丘师范学院学报》2004,20(5):58-59
如果一个图的顶点集可以划分为基数尽可能相等的k个独立集。则称该图是可均匀k-着色的.本文得到了毛虫树可均匀k-着色的一个充要条件. 相似文献
7.
图G的一个k全染色是用k种颜色对图G的顶点集和边集进行染色使得相邻接的或相关联的元素染不同的颜色,图G的全色数χ"(G)为图G的k-全染色中的最小k值.Behzad和Vizing猜想任意简单图G的全色数都不超过Δ(G)+2,已经证明了此猜想对最大度不是6的平面图成立,而且最大度不小于9的平面图G的全色数为Δ(G)+1.本文利用差值转移方法研究了最大度小于9的一些情况,证明了最大度为4,5,6,7,8的平面图G,如果其围长不小于8,则其全色数也为Δ(G)+1. 相似文献
8.
李雪峰 《廊坊师范学院学报(自然科学版)》2009,9(3):7-8
图G的色数Х(G)是指对图G进行着色并使相邻顶点具有不同颜色的最少颜色数,若对G的任意真子图H有Х(H)〈Х(G)=k,则称G是k-色临界的,因此可以给出一种构造k-色临界图的方法。 相似文献
9.
对于图G的正常k-全染色f称为G(V,E)的k-均匀全染色,当且仅当任意2个色类中的元素总数至多相差1.χet(G)=min{k|G有k-均匀全染色}称为图G的均匀全色数.利用均匀边染色的相关结论,讨论并得到了图Sn+Fn和Sn+Wn的均匀全色数. 相似文献