首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 78 毫秒
1.
图G的k-全染色是用k种颜色对图G的V(G)∪E(G)中的元素进行着色, 使得相邻或者相关联的两个元素染不同的颜色, 图G的全色数是使G存在k-全染色的最小整数k. 对最大度为Δ的平面图, 如果(1),Δ(G)≥5且任何点至多关联一个长度至多为5的圈, 或者(2),Δ≥4, 不含3-圈并且任何点至多关联一个长度至多为6的圈, 则它的全色数为Δ(G)+1。  相似文献   

2.
设G为n≥1 阶简单无向图,ρ(G)和μ(G)分别表示图G的邻接谱谱半径和Laplacian谱谱半径.利用生成偶子图证明了:当k为偶数时,ρ(G)≤(k-1)/kμ(G);当k为奇数时,ρ(G)≤k/(k+1)μ(G).其中k(≥1)为简单图G的色数.  相似文献   

3.
给定一个平面图G,χ´l(G)和χ"l(G)分别表示图G的列表边色数和列表全色数.证明了:如果一个平面图G满足Δ(G)≥7,并且任何一个三角形至多和一个其他的三角形相邻,则有χ´l(G)≤Δ(G)+1和χ"l(G)≤Δ(G)+2成立。  相似文献   

4.
图的点可区别IE-全色数的一个上界   总被引:4,自引:2,他引:2  
用概率方法研究图的点可区别IE-全色数的一个上界,得到:如果δ≥7且16Δ≤n≤Δ7/[32×105(Δ+1)] +1, 则χievt(G)≤16Δ ,这里n是G的阶,δ是G中点的最小度数,Δ是G中点的最大度数。    相似文献   

5.
构造了洞指数ρ(G)≥1的一类2-稀疏连通图的补图的两个不同的岛序列。  相似文献   

6.
给出了图的孤立韧度I(G)与分数[a,b]-因子存在性间的关系,证明了若δ(G)≥I(G)≥a-1+(a-1)/b,其中a、b均为整数,2≤a<b,则图G有分数[a,b]-因子。进一步证明该结论在一定意义下是最好的,并且提出猜想当a=b时结论仍然成立。  相似文献   

7.
设G是一个n阶2连通图,整数a,b满足2≤a<b,g(x)和f(x)是定义在V(G)上的两个非负整数值函数,使得x∈V(G),满足a≤g(x)2-(a-1)(b-a)]/(a-1),[n>(a+b-3)(a+b-2)]/(a-1), 且max{dG(x) ,dG(y) }≥(b-1)n/(a+b-2)对G中任意两个不相邻的顶点x,y都成立。  相似文献   

8.
如果图G中任意一对距离为2的顶点x,y,有J(x,y)∪J′(x,y)≠Φ,则称G为P3-支配图。本文证明了:设G是n(≥3)阶2-连通P3-支配图,如果对G中任意一对不相邻的顶点x,y,有2|N(x)∪N(y)|+d(x)+d(y)≥2n-5,则G含有Hamilton圈或者G∈{K2,3,K1,1,3}。  相似文献   

9.
本文提出顶点染色的一个猜想:χ(G)≤S+C,其中χ(G)和S分别是一个图的顶点染色数和最大团的顶点数;C是常数且C∈Z+。若C=1,p为图G的顶点数,我们证明对于S=p-6的一些图,有χ(G)≤p-5。  相似文献   

10.
若干倍图的Smarandachely邻点边染色   总被引:1,自引:0,他引:1  
图G(V,E)的Smarandachely邻点边色数是满足条件uv∈E(G),|C(u)\C(v)|≥1并且|C(v)\C(u)|≥1的一个正常边染色的最小边色数,其中C(u)={f(uv)|uv∈E(G)}。给出了路、圈、星、扇图的倍图的Smarandachely邻点边色数。  相似文献   

11.
非空图G的约束数b(G)是指使得图G的控制数γ(G)增大而删除的最少的边数.[Fischermann M, Rautenbach D, Volkmann L. Remarks on the bondage number of planar graphs. Discrete Math,2003,260:57-67\]已经证明,对于一个围长为g(G)的平面图G,如果g(G)≥4则b(G)≤6,如果g(G)≥5则b(G)≤5,如果g(G)≥6则b(G)≤4,如果g(G)≥8则b(G)≤3.我们把这个结果推广到连通的超环面图中.  相似文献   

12.
提出图的星边星-全染色的概念,图G的一个正常全染色被称为星边星-全染色,如果对G中点进行星染色,边进行星边染色.并定义图的星边星-全色数,记为χsTs(G).用构造染色的方法给出一些特殊图(路,圈,轮,扇,完全图)的星边星-全色数.同时运用概率方法给出满足一定条件的图G的星边星-全色数的一个上界,即若图G的最大度Δ(G)≥30,则χsTs(G)≤24(Δ-1)3/2.  相似文献   

13.
提出了图的邻点可区别星边染色及邻点可区别星边色数χ’ass(G)的概念,并用Lovász局部引理证明了若G=(V,E)是一个最小度为δ(G)≥3的简单无向图,则χ’ass(G)≤「32Δ32?。  相似文献   

14.
设G=(V,E)是一个图。集合S■V称为一个k-分支限制控制集,如果S是一个限制控制集且G[S]最多有k个分支。G的k-分支限制控制数是G的最小k-分支限制控制集的基数,记作γkr(G)。证明了若树T有n个顶点,则γkr(T)≥max{「n+2/3┐,n-2(k-1)},而且刻画了可以达到这个下界的树。  相似文献   

15.
点关联较少3-面的平面图的全染色   总被引:1,自引:0,他引:1  
证明了对每点至多关联2个3-面的平面图,全染色猜想成立. 对每点至多关联2个3-面且Δ(G)≥8的平面图,有xT(G)=Δ(G)+1.对每点至多关联[Δ(G)/2」个3-面且Δ(G)≥9的平面图,有xT(G)=Δ(G)+1.  相似文献   

16.
证明了(1)若图G是二部图,则当r≥s(χ’(G)-1)+2时,χr,s,1(G)=χr,0,0(G);(2)若图G是非二部图,则当r≥sχ’(G)/χ(G)-s+1且r不是s的倍数时,χr,s,1(G)=χr,0,0(G);(3)当Δ(G)≥2,χ’(G)=Δ(G),且s≥2r,r≥2t时,χr,s,t(G)=χ0,s,0(G);(4)当χ’(G)=Δ(G)+1且s-t≥r≥t时,χr,s,t(G)=χ0,s,0(G)。  相似文献   

17.
图G的线性荫度是一种非正常的边染色,即它的边集合E(G)可以分割成线性森林的最小数量,用la(G)表示。主要研究最大度Δ(G)≥7且可嵌入到欧拉示性数非负曲面图G上的线性荫度,证明了如果图G中不含相邻的含弦6-圈,则图G的线性荫度为「Δ/2。  相似文献   

18.
图G的一个点染色称为单射染色,如果任何两个有公共邻点的顶点染不同的颜色.一个图G称为单射k-可选择的,如果对于顶点V(G)的任何一个大小为k的允许颜色列表L,都存在一个单射染色φ,使得对于v∈V(G),有φ(v)∈L(v).使得G为单射k-可选择的最小k,称为G的列表单射染色数,记作χ_i~l(G).设G是最大度为Δ,围长为g的可嵌入到欧拉示性数χ(Σ)≥0的曲面Σ的一个图.证明了若Δ≥7且g≥6,则χ_i~l(G)≤Δ+3.  相似文献   

19.
设图G是n阶简单连通图.如果G的支配数为1,则G是上可嵌入的.如果G是2-边连通且G的支配数为2,则G是上可嵌入的.如果G是3-边连通且G的支配数为3,则G的最大亏格介于|(β(G)-2)/2|和|β(G)/2|之间,其中β(G)=|E(G)|-|V(G)|+1.论文得到了一些在控制数和边连通度条件下的最大亏格的界.  相似文献   

20.
图G的平方G2定义为顶点集V(G)=V(G2), 并且uv∈E(G2)当且仅当u和v之间的距离至多为2. G2的色数χ(G2)是指使得G2存在正常k顶点染色的最小整数k. 用权转移的方法证明: 如果mad(G)<4且Δ(G)≥7, 则χ(G2)≤3Δ(G)+1;  如果mad(G)≤4且Δ(G)≥8, 则χ(G2)≤3Δ(G)+5.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号