共查询到20条相似文献,搜索用时 15 毫秒
1.
张埂 《烟台大学学报(自然科学与工程版)》2013,26(4):243-245,249
图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3. 相似文献
2.
如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数。利用差值转移方法并结合平面图的结构性质,证明了不含相交三角形和4圈的平面图的无圈边色数不超过△(G)+6。 相似文献
3.
郑丽娜 《浙江师范大学学报(自然科学版)》2012,(1):32-36
无圈边染色是指图G的一个正常边染色,使其不产生双色圈.研究了不含特殊短圈平面图的无圈边染色问题,证明了:如果平面图G不含4到8-圈,那么G的无圈边染色数不大于Δ(G)+1. 相似文献
4.
图G的无圈边染色是图论染色的重要研究对象,为得到平面图的无圈边色数的上界,利用差值转移方法和平面图的结构性质,证得了不含相交三角形的平面图的无圈边色数不超过Δ(G)+6。 相似文献
5.
图的无圈边染色是图的染色理论中的一个重要问题,2001年,Alon等猜想任意简单图G的无圈边色数都不超过△(G)+2,其中△(G)为图G的最大顶点度。为了研究该猜想对平面图是否成立,利用差值转移方法,证明了不包含三角形的平面图G的无圈边色数不超过△(G)+3. 相似文献
6.
丁伟 《山东大学学报(理学版)》2012,47(6):76-79
如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数。利用已有的关于平面图的结构性质,证明了不含4圈的2-连通平面图的无圈边色数不超过Δ(G)+11。 相似文献
7.
张埂 《黑龙江科技学院学报》2010,20(4):315-317,322
为了研究简单图G的无圈边染色,利用线性一时间算法思想证明了最大顶点度为4的简单图G。如果G中任意一条边的两个端点的度数之和不超过6,则其无圈边色数不超过5。 相似文献
8.
主要研究了平面图的无圈边染色问题。证明了对平面图G,如果G不包含3,5圈,且G中任意两个4-圈都不共边,则无圈边染色猜想成立;并且,如果G不含3-圈,且任意两个4-圈不共点,则G的无圈边染色数不大于Δ(G)+3。 相似文献
9.
10.
11.
对无孤立边的简单图G,设G是一个正常边染色,如果G中任何两种颜色导出的子图是森林,即G中没有双色圈,且相邻点所关联的色集合不同,则称之为图G的邻点可区别无圈边染色。本文应用Lovász局部引理,即概率的方法确定了图G的一个邻点可区别无圈边染色的上界。 相似文献
12.
卞量 《曲阜师范大学学报》2008,34(1):43-47
提出了邻点可区别无圈边染色的概念及其相关猜想,并证明了对于一个没有孤立边的图G,如果它的邻点可区别边染色数X'as(G)=ε,那么存在一个常数r,如果围长g(G)≥r△log△,那么G的邻点可区别无圈边染色数至多为ε 1. 相似文献
13.
为研究图的无圈边色数与图的最大平均度之间的关系,利用差值转移方法和最小反例图的一些结构性质,证明了最大平均度不小于7/2的简单图G,如果其最大度不小于6,则其无圈边色数不超过Δ(G)+2. 相似文献
14.
利用差值转移的方法证明了,如果g(G)≥4则有X′a≤Δ(G)+4.图G=(V,E)是简单图,映射C:E→[k],被称作是图G的一个无圈k边染色.如果任意相邻的两个边染有不同的颜色,以及图G中不含有2-色圈,换句话说即图G中任何染两种颜色的边的导出子图是一棵森林. 相似文献
15.
根据图的邻点可区别无圈边染色的定义,利用构造的方法讨论联图Pm∨Wn、Pm∨Fn、Pm∨Pn、Pm∨Sn和Cm,n的邻点可区别无圈边染色,并给出它们的邻点可区别无圈边色数及其证明,且均满足图的邻点可区别无圈边染色猜想. 相似文献
16.
不含4圈的平面图的无圈边色数的新上界 总被引:1,自引:0,他引:1
为了研究平面图的无圈边染色,利用差值转移方法并结合平面图的结构性质,证明了不含4圈的平面图的无圈边色数不超过Δ(G)+6. 相似文献
17.
18.
考虑使得图G存在无重复的k-重n-染色的所有数对(n,k),其比值n/k的下确界定义为图G的无重复分数染色数.圈图的无重复分数染色数在文献中已有研究,除了C10,C14和C17之外的所有圈图的无重复分数染色数都已被确定,讨论并给出了这3个圈图的无重复分数染色数的上下界. 相似文献
19.
讨论了无三角形的边染色图中的正常染色的路和圈,在无三角形图中改进了原有的结果。证明了在顶点的最小色度至少为d(d≥2)的条件下,边染色图G或者存在长至少为4d-2的正常染色的路,或者存在长至少为2「2d/3的正常染色的圈。 相似文献
20.
一个图G的无圈边染色是一个正常的边染色,使得不产生双色圈.Fiamˇcik和Alon等分别提出了著名的无圈边色数猜想:每一个简单图G是无圈边(Δ+2)可染的,其中Δ是G的最大度.证明了对于不含3圈和5圈相邻的平面图猜想成立. 相似文献