首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 0 毫秒
1.
证明了,任意正整数k≥2,存在点可区别边色数为2k+1的k+1-正则图;任意正整数m≥4,存在点可区别边色数为m的偶图.  相似文献   

2.
1968年,Vizing提出猜想:边染色临界图的独立数不大于其阶数的一半.针对不含2度点的边染色临界图,本文证明当最大度为9,10时,独立数α(G)≤(3△-3)/(5△-3)|V|和当△∈{11,…,46}时,独立数α(G)≤(15△-42)/(23△-42)|V|.  相似文献   

3.
研究正则图的均匀边染色,指出并非所有正则图都存在任意种颜色的均匀边染色.证明当l能够分解为整数k与偶数b的乘积时,l-正则图存在均匀k-边染色.同时,给出正则图均匀边染色的最小颜色数.  相似文献   

4.
设G是无割点平面图,xefl(G)为G的边面List选择数。本文证明了若G为最大度Δ(G)≥6的无割点外平面图,则xefl(G)=Δ(G)。  相似文献   

5.
如果一个连通的第二类图G去掉任意一条边后其边色数都比图G小,则称它是一个临界图.最大顶点度为△的临界图称作△-临界图.1968年,Vizing猜想任意n阶△-临界图G边数m的下界为(nΔ-n+3)/2.Fiorini不等式和差值转移法被广泛用于研究此猜想.笔者利用Vizing邻接引理和临界图的结构性质给出了Δ-临界图在△≥6且(Δ-1)度顶点至多邻接一个四度顶点时Fiorini不等式的一个新的下界.  相似文献   

6.
设σ是G的一个k-点染色,若在G中一定存在一个点,使得该点在其他k-1个色类中都至少有一个邻居,则称该点为b-点,称σ为G的一个b-染色.其中,最大的k值称为G的b-色数,记为φ(G).设σ是G的一个k-边染色,若在G中一定存在一条边,使得该边在其他k-1个色类中都至少有一个邻居,则称该边为b-边,称σ为G的一个b-边染色.其中,最大的k值称为G的b-边色数,记为φ’(G).  相似文献   

7.
研究了Halin 图的有点面约束的边染色,给出了Halin 图的有点面约束的边染色色数的一个精确结果.  相似文献   

8.
为了研究简单图G的无圈边染色,利用线性一时间算法思想证明了最大顶点度为4的简单图G。如果G中任意一条边的两个端点的度数之和不超过6,则其无圈边色数不超过5。  相似文献   

9.
图G的染色数X(G)是使得G中任何相邻两点均染不同色的最小颜色数。文中证明了,如果ω(G)≥6,△(G)=ω(G)+1,ㄧV(G)ㄧ≤2ω(G)+1,则X(G)=ω(G),给出了两个图G0,G1,使得ㄧV(G0)ㄧ=14,ω(G0)=6,△(G0)=7,X(G0)=7;ㄧV(G1)ㄧ=11,ω(G1)=5,△(G1)=6,X(G1)=6。  相似文献   

10.
1968年,Vizing提出了关于临界图的独立数猜想:若G是n阶的Δ-临界图,则有α(G)≤n/2.利用Vizing邻接引理研究这一猜想,给出了3-临界图的一个上界.  相似文献   

11.
图G的一种均匀k-边染色是指用k种颜色去染G的边使得对G的每一个顶点v,任何两种颜色染与。相关联边的数目最多相差1.证明了对任意的大于3的整数k,Halin图都有均匀k-边染色;讨论了k=3的情况.  相似文献   

12.
讨论了3一致φ-超图的最小边数问题,给出了上色数为2的3一致φ-超图的最小边数的一个上界。  相似文献   

13.
设G是一个简单图,f是G的一个k-正常边染色,又满足对任意的uv∈E(G),都有C(u)≠C(v),则称f为G的一个邻强边染色,简称k-ASEC,且称χas(G)=min{k|G存在k-ASEC}为G的邻强边色数,其中C(u)={f(uv)|uv∈ E(G)}.给出了路.圈、树、完全图、完全二分图、星、扇、轮的冠的邻强...  相似文献   

14.
图G的染色数X(G)是使得G中任何相邻两点均染不同色的最小颜色数.文中证明了:如果ω(G)≥6,△(G)=ω(G)+1,|V(G)|≤2ω(G)+1,则X(G)=ω(G),给出了两个图G0、G1,使得|V(G0)|=14,ω(G0)=6,△(G0)=7,X(G0)=7;|V(G1)|=11,ω(G1)=5,△(G1)=6,X(G1)=6.  相似文献   

15.
如果一个连通图不包含长度大于或等于4的圈,那么这个图被称为花形图,在这篇文章中,我们证明了每一个花形图的对策染色数至多为5。  相似文献   

16.
图G的一种均匀k 边染色是指用k种颜色去染G的边使得对G的每一个顶点v ,任何两种颜色染与v相关联边的数目最多相差 1.证明了对任意的大于 3的整数k,Halin图都有均匀k 边染色 ;讨论了k=3的情况  相似文献   

17.
图的染色是图论的重要研究内容之一.平面图染色是其中的一个主要方面.有各种各样的染色方式,近来,又出现了列表染色[1].定义1称图G是k-边可选择的.如果任给e∈E(G),和边e的任给颜色集L(e),|L(e)|=t,都可以选一种颜色σ(e)∈L(e)...  相似文献   

18.
研究了树、圈、完全二部图和轮图的2-强边染色问题.对于树,给出了2-强边色数等于最大顶点度加1的充分条件;对于圈、完全二部图及轮图,求出了2-强边色数,并给出了相应的染色方案.  相似文献   

19.
设G是简单图,f是从V(G)∪E(G)到{1,2,…,k]的一个映射.对每个u∈V(G),令C(u)={f(uv)|v∈V(G),uv∈E(G)].如果f是k-正常边染色,且对任意u,v∈V(G),有C(u)≠C(v),那么称f为图G的点可区别边染色(简称为k-VDEC).数x's(G)=min{k|G有k-VDEC}称为图G的点可区别边色数.本文通过应用概率方法,证明了对任意最大度△≥2的图G,x's(G)≤16△.  相似文献   

20.
本文证明了:若G为简单外平面图,则(i)当Δ(G)≥4时,Δ(G)≤Xe(G)≤Δ(G)+1;(ii)当Δ(G)=3时,4≤Xe(G)≤5,且Xe(G)=5当且仅当G-E'含有奇圈分支,其中E'为G的割边集合,Δ(G)为G的点最大度,Xe(G)为G的边面全色数。  相似文献   

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

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