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

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

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

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

两类n-部图及其补图的无圈染色

图G的无圈染色是满足任意两个色类的并的导出子图不含圈的正常点染色.G的无圈染色所用最少的颜色数称为G的无圈色数,记为a(G),从而得到了两类n-部图及其补图的无圈色数.     

不含特殊短圈平面图的无圈边染色

无圈边染色是指图G的一个正常边染色,使其不产生双色圈.研究了不含特殊短圈平面图的无圈边染色问题,证明了：如果平面图G不含4到8-圈,那么G的无圈边染色数不大于Δ（G）＋1.     

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

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

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

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

一些平面图的无圈边染色

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

图的邻点可区别无圈边染色

对无孤立边的简单图G,设G是一个正常边染色,如果G中任何两种颜色导出的子图是森林,即G中没有双色圈,且相邻点所关联的色集合不同,则称之为图G的邻点可区别无圈边染色。本文应用Lovász局部引理,即概率的方法确定了图G的一个邻点可区别无圈边染色的上界。     

平面图的无圈边染色

利用差值转移的方法证明了,如果g（G）≥4则有X′a≤Δ（G）＋4.图G=（V,E）是简单图,映射C：E→[k],被称作是图G的一个无圈k边染色.如果任意相邻的两个边染有不同的颜色,以及图G中不含有2-色圈,换句话说即图G中任何染两种颜色的边的导出子图是一棵森林.     

圈的无重复分数染色

考虑使得图G存在无重复的k-重n-染色的所有数对(n,k),其比值n/k的下确界定义为图G的无重复分数染色数.圈图的无重复分数染色数在文献中已有研究,除了C10,C14和C17之外的所有圈图的无重复分数染色数都已被确定,讨论并给出了这3个圈图的无重复分数染色数的上下界.     

图的分数着色和分数色数

引入了一种新的图着色 :图的分数关联着色。定义了图的分数关联色数。讨论了分数关联着色的性质 ,给出了图的分数关联色数的一个下界。     

图的边覆盖染色与分数边覆盖染色

讨论了图G=(V,E)的分数边覆盖色数χ′cf(G)的概念和性质,给出计算χ′cf(G)的一个精确公式,即χ′cf(G)=minS2·|C[S]||S|+1,其中S为V(G)的非空子集且|S|为奇数,C[S]是E(G)的至少有一个端点在S中的边构成的子集,并证明δ-1<χ′cf(G)δ;同时讨论了χ′cf(G)与图G的边覆盖色数χ′c(G)的关系,并利用χ′cf(G)与χ′c(G)的关系对图进行分类.     

图的条件色数的上界

得到了图的条件色数的上界和达到上界的图类.主要结论是:x,(G)≤△2 1,等号成立的充分必要条件是图G为Moore图,即圈G5,Petersen图,Hoffman-Singleton图,以及可能存在的57度正则图.     

图的强染色

研究了简单图G（V，E）的强色数Xs(G）的上界与极图及Xs(G)与全色数XT（G）的关系;得到了一些特殊图的强色数Xs(G).     

最大度为5的平面图的2-距离列表染色

讨论了最大度为5的平面图G的2-距离列表染色问题.给出了图G的2-距离列表色数χl2(G)的一些性质:1)若g(G)≥6,则χl2(G)≤11;2)若g(G)≥7,则χl2(G)≤9;3)若g(G)≥8,则χl2(G)≤8.其中,g(G)为图G的围长.     

关于Mycielski图的点可区别均匀全染色

研究了一些Mycielski图的点可区别均匀全染色(VDETC), 利用构造法给出了路、圈、星和扇的Mycielski图的点可区别均匀全色数, 验证了它们满足点可区别均匀全染色猜想(VDETCC)。     

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

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