共查询到19条相似文献，搜索用时 156 毫秒
1.
李雪峰 《河北职业技术学院学报》2009,(3)
图G的色数χ(G)是指对图G进行着色并使相邻顶点具有不同颜色的最少颜色数,若对G的任意真子图H有χ(H)<χ(G)=k,则称G是k—色临界的,因此可以给出一种构造k—色临界图的方法。 相似文献
2.
任意给定图G的一个k-一致列表L,若G是L-可染的,且满足每种颜色至多在「｜V（G）/k｜」个点上出现,则称G是k-均匀可选择的．若图G有一个正常k-顶点染色满足任两个色类中的顶点数至多相差1,则称G是k-均匀可染的．应用discharge方法讨论了不含3-圈和4-圈的平面图的结构,证明了对于不含3-圈和4-圈的平面图G,当k≥{max△（G）,6）时,G是k-均匀可选择的,同时G也是k-均匀可染的． 相似文献
3.
设k和d是2个互素的正整数且k≥2d．G^dk是一个图,它的顶点集合为{0,1,…,k-1},边集合为{ij｜d≤｜i-j｜≤k-d,i,j=0,1,…,k-1}．图G的圆色数χc（G）定义为使得图G与G^dk同态的2个正整数k和d的最小比值k／d．研究了χc（G）和χc（G-v）之间的关系,对任意顶点v求出了χc（G^dk-v）的精确值,给出了具有对任意顶点χc（G-v）=χc（G）-1和其他特定性质的图类;并对图的圆色数的一些下界进行了探讨,给出了图的圆色数达到下界χc-1＋1／d的充要条件,这里χ和α分别是图G的点色数和独立数． 相似文献
4.
对于图G的正常k-全染色f称为G（V,E）的k-均匀全染色,当且仅当任意2个色类中的元素总数至多相差1.χet（G）=min{k｜G有k-均匀全染色}称为图G的均匀全色数.利用均匀边染色的相关结论,讨论并得到了图Sn＋Fn和Sn＋Wn的均匀全色数. 相似文献
5.
图G的一种P－着色是分配颜色到它的顶点，使得同一色类的导出子图具有性质P，图G的P－色数χ（G，P）是G的具有k种颜色的P－着色的最小数k。研究了当P这一性质是禁止路Pj时的P－色数，且把这一色数记作χ（G，^┐Pj)，给出了一些特殊图类χ（G，^┐Rj）的值。 相似文献
6.
董伟 《商丘师范学院学报》2006,22(2):68-69
图G=(V,E)的一个正常k-着色实际上是将G的顶点划分为独立集,记为∏={V1,V2,…,Vk}.其中Vi,i=1,2,…,k,也称色类.对于任一色类Vi中的点v,如果它与其余色类中至少一个点相邻,则v被称为是满色的.如果在G的一个正常k-着色中,所有点都是满色的,则称这样的着色是满着色.如果一个图存在满着色,定义图的满着色数为使得图存在满着色的最小颜色数,记为χf(G).另外,记ψf(G)为使图存在满着色的最大颜色数.本文主要研究了有关满着色的一些性质,并给出一个满着色与完美图之间的结论. 相似文献
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.
设P（G,λ）是图G的色多项式,若对于任意与图G的色多项式相等（P（G,λ）=P（H,λ））的图H都与图G同构（G≌ H）．则称图G是色唯一图;这里通过比较t部图的t十1类的划分数,证明了若 相似文献
9.
如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色.图G的无圈边色数表示图G的无圈边染色所需的最小颜色数.为研究平面图的无圈边色数的上界,利用差值转移方法并结合平面图的结构性质,证明了不含相交三角形的平面图的无圈边色数不超过Δ（G）＋7. 相似文献
10.
研究简单图的笛卡尔积图的无圈边染色及最小色数（标记为＇a（G））的问题,利用图分解、构造染色等方法给出了G×H,4G×C4,T1×T2×…×Tn,Qn等笛卡尔积图的无圈边色数. 相似文献
11.
给定非负整数r,s和t,简单图G=（V,E）的一个[r,s,t]-着色是从集合V∪E到色集{0,1,2…,k-1}的映射c,使得对任意相邻的两点vi,vj有︱c（vi）-c（vj）︱≥r,对任意相邻的两边ei,ej,有︱c（ei）-c（ej）︱≥s,对相关联的任意点vi和边ej,有︱c（vi）-c（ej）︱≥t.图G的[r,s,t]-色数r,s,t（G）定义为使得图G存在[r,s,t]-着色的最小的整数k.本文给出了参数r=0和r=t=1的[r,s,t]着色的几个结果. 相似文献
12.
高炜 《昆明师范高等专科学校学报》2012,(6):5-9
若删除G中任意一个独立集后得到的图依然是分数（g,f,m）-消去图,则称G为分数ID-（g,f,m）-消去图．将若干个关于分数消去图邻域并条件的结论推广到分数ID-消去图,证明了如下两个结论：1）阶为n的图G满足n≥12k＋6m-11,6（G）≥n/3＋k＋m,且／NG（x）UG（y）/≥2n/3对G中任意一对不相邻的顶点x,y都成立,则G是分数ID-（k,m）-消去图;2）若δ（G）≥（an/2a＋b）＋（b2（i-1）/a＋2m,n〉（（2a＋b）[i（a＋b）＋2m-2]）/a,且/NG（x1）u…uNG（x1）/≥（a＋b）n/2a＋b,对V（G）的所有独立集{x1,……,xi}都成立．则G是分数ID-（g,f,m）-消去图． 相似文献
13.
设图G是一简单的且有完美匹配的连通图.称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(V(G)-2)2)的偶匹配M都可以扩充为G的一个完美匹配.本文主要刻画了Harary图的k-偶匹配可扩性:对于任意的n,如果r(r>4)是偶数,那么Hr,2n是2-偶匹配可扩的等等. 相似文献
14.
呼勇 《延安教育学院学报》2008,22(4):69-70
设G是二分图,k1,k2,…,km是正整数。若二分图G的边能划分成m个边不交的[0,k1]-因子F1,…,[0,k]-因子Fm,则称F^-={F1,…,Fm}是二分图G的一个[0,ki]1^m-因子分解,又若H是二分图G的一个有m条边的子图,若时任意的1≤i≤m有｜E（H）∩E（Fi）｜=1,则称F^-与H是正交的。本文主要研究二分图的正交[0,ki]1^m-因子分解,并给出一个结果。 相似文献
15.
连通图G的孤立断裂度定义为isc（G）=max{i（G-S）-｜S｜：S∈C（G）},其中i（G-S）是G-S中的孤立点数,C（G）是G的点割集。本文给出了平衡二部图的孤立断裂度以及图的孤立断裂度与图的哈密顿性的关系。 相似文献
16.
17.
研究了两个均同构于完全二部图Km,n的图G1=(X1,Y1)与G2=(X2,Y2)的匹配和Bm,n的L(2,1)-标号问题,得到了下面的结果:(1)若X1中元素完全与X2中元素相匹配且m,n>3,则Bm,n的L(2,1)-标号数为m+n;(2)若X1中元素不完全与X2中元素相匹配且m,n>6,则Bm,n的L(2,1)-标号数为m+n+1. 相似文献
18.
设j,k和m是3个正整数.给定一个图G.设f：V（G）→{0,1,…,m-1}是一个映射.如果对图G的任意一对相邻顶点u和v都有f（u）-f（v）m≥j,对任意一对距离为二的顶点都有f（u）-f（v）m≥k,其中a-bm=min{a-b,m-a-b},则称f是图G的一个圆m-L（j,k）-标号.使得图G有圆m-L（j,k）-标号的最小的正整数m称为图G的圆L（j,k）-标号数,记为σj,k（G）.对任意2个满足j≤k的正整数,确定了树以及2个完全图的笛卡尔乘积图和直积图的圆L（j,k）-标号数. 相似文献
19.
莫明忠 《洛阳师范学院学报》2013,32(2):7-10
两个不交图G与H的联G+H是指顶点集为V(G)∪V(H),边集为E(G)∪E(H)∪{xy|x∈V(G),y∈V(H)}的图.证明了当n=m+1时,联图Om+Cn是第二类图,否则,Om+Cn是第一类图;当|n-m|=1时,联图Cm+Cn是第二类图,否则,Cm+Cn是第一类图. 相似文献