一些平面图的无圈边染色

主要研究了平面图的无圈边染色问题。证明了对平面图G,如果G不包含3,5圈,且G中任意两个4-圈都不共边,则无圈边染色猜想成立;并且,如果G不含3-圈,且任意两个4-圈不共点,则G的无圈边染色数不大于Δ(G)+3。     

不含4圈的平面图的无圈边染色

如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数。利用已有的关于平面图的结构性质,证明了不含4圈的2-连通平面图的无圈边色数不超过Δ(G)+11。     

不含相交三角形和4圈的平面图的无圈边染色

如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数。利用差值转移方法并结合平面图的结构性质,证明了不含相交三角形和4圈的平面图的无圈边色数不超过△(G)+6。     

平面图的无圈边染色

一个图G的无圈边染色是一个正常的边染色,使得不产生双色圈.Fiamˇcik和Alon等分别提出了著名的无圈边色数猜想:每一个简单图G是无圈边(Δ+2)可染的,其中Δ是G的最大度.证明了对于不含3圈和5圈相邻的平面图猜想成立.     

不含相交三角形的平面图的无圈边色数的新上界

图G的无圈边染色是图论染色的重要研究对象,为得到平面图的无圈边色数的上界,利用差值转移方法和平面图的结构性质,证得了不含相交三角形的平面图的无圈边色数不超过Δ(G)+6。     

不含3,4圈的平面图的无圈边染色的一个结果

利用差值转移方法研究了不含3圈,4圈的平面图的无圈边染色,证得了它们的无圈边色数不超过Δ(G)+2。     

不含3圈的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题,2001年,Alon等猜想任意简单图G的无圈边色数都不超过△（G）＋2,其中△（G）为图G的最大顶点度。为了研究该猜想对平面图是否成立,利用差值转移方法,证明了不包含三角形的平面图G的无圈边色数不超过△（G）＋3．     

不含三角形的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3.     

不含4圈的平面图的无圈边色数的新上界

 为了研究平面图的无圈边染色,利用差值转移方法并结合平面图的结构性质,证明了不含4圈的平面图的无圈边色数不超过Δ(G)+6.     

平面图无圈边着色的一个结果

图G的无圈边着色是指图G的一个正常边着色且不含双色的圈.图G的无圈边色数是指图G的无圈边着色中所用色数的最小者,用x’a(G)表示;证明了如果G是一个D中的顶点不与3-面相关联,3-顶点不与D中的顶点相邻且Δ(G)≥6的平面图,则x’a(G)≤Δ(G)+1。     

伪Halin-图的无循环边着色

图G的无循环边着色是指图G的正常的边着色且任意的圈上不着双色.图G的无循环边色数是指对G进行无循环边着色所需的最少色数k,记为a′(G).给出了伪Halin图的无循环边色数满足猜想a′(G)Δ(G)+2,并且对任意的伪Halin图G且G≠K4,有a′(G)=Δ(G).     

图的无圈边染色的一个结果

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

围长≥7最大度≥5的平面图的无圈列表边染色

对图G的一个正常边染色,如果图G的任何一个圈至少染3种颜色,则称这个染色为无圈边染色.若L为图G的一个边列表,对图G的一个无圈边染色φ,如果对任意e∈E(G),都有φ(e)∈L(e),则称φ为无圈L-边染色.用a′_(list)(G)表示图G的无圈列表边色数.论文证明:若图G是一个平面图,且它的最大度Δ≥5,围长g(G)≥7,则a′_(list)(G)=Δ.     

图的点可区别无圈边色数的一个上界(英文)

图G的一个正常边染色f,若满足:1)G中无2-色圈;2)对于V(G)中的任意两点u和v,有C(u)≠C(v),这里C(u)={f(uw)|uw∈E(G)},则f叫做图G的一个点可区别无圈边染色.图G的点可区别无圈边色数,记为χ′_(vda)(G),是图G的一个点可区别无圈边染色所用色的最小数目.证明了若图G是一个最小度不小于5,且顶点数不超过30Δ~4的图时,χ′_(vda)(G)≤10Δ~2,其中Δ是图G的最大度.     

基于最大平均度的图的无圈边染色

为研究图的无圈边色数与图的最大平均度之间的关系,利用差值转移方法和最小反例图的一些结构性质,证明了最大平均度不小于7/2的简单图G,如果其最大度不小于6,则其无圈边色数不超过Δ(G)+2.     

最大度为4的外平面图的无圈边色数

一个图G的无圈边染色是一个正常的边染色,使得任一个圈上至少有3种不同的颜色.G的无圈边色数a＇（G）是使得G有无圈k-边染色的最小整数k.设G是一个最大度为4的外平面图.对于现有结果 4≤a＇（G）≤5中,何时为4,何时为5,还没有一个完整的刻画.给出一个使得a＇（G）=4的充分条件,拓展了该领域的相关结果.