具有最小子树数目的单圈图与双圈图

运用删边缩边原理,探讨了3种减小子树数目的变形,每一种变形都能比较一组图的子树数目的大小。在利用这些变形的基础上,刻画了具有最小子树数目的单圈图和双圈图的结构。     

Halin图和Series-Parallel图的动态色数

图的动态着色是Bruce Montgomery于2001年引入的一个新概念。本文分别证明了Halin图和非5圈的Series—Parallel图的动态色数都不超过4。     

单圈图和双圈图的次大次小约化Sombor指标

首先,利用图形变换及独特的分类方法解决n(n≥5)阶单圈图的约化Sombor指标最大、次大和次小以及对应的极图问题;其次,考虑n(n≥6)阶双圈图的约化Sombor指标次大、次小以及对应的极图问题,给出n(n≥5)阶单圈图最大、第二大以及第二小的约化Sombor指标,并刻画对应的极图;同时还确定了n(n≥6)阶双圈图第二大和第二小的约化Sombor指标及所对应的极图.     

具有给定色数的互补图的实现

本文给出关于三元组(p;m,x)的充分必要条件,在此条件下,存在p点的图G,使图G及其补图()的点色数(或边色数)分别是m和n。     

图乘积的分数色数

在文中我们对两个图的强乘积的分数色数进行了研究.任意给定两个图G和H,我们证明了ω(G)ω(H)≤χf(GH)≤χ(G)χ(H),这里ω(G)表示图G的最大团所含顶点的个数,χf(G)和χ(G)分别表示图G的分数色数和色数.从而我们可以通过图G和H本身的性质来对它们的强乘积的分数色数和色数进行估计.     

图的色数与其补图边色数的关系

本文对图的点色数与其补图边色数的关系进行了考察.     

两类距离图的分式色数和点色数

分式色数和,点、色数是图的两个重要参数.本文在文献[1]的基础上给出了两类距离图G(Z,Dm,k,k+1)与G(Z,Dm,kk+1,K+2)的分式色数和点色数.     

广义-Mycielski图的集合点色数

图G的集合点染色是集合X中的非空子集在点集V(G)上的一个分配,满足相邻点的色集合不相同、相邻点上色集合交不为空集,且每个点上的色集合长度不低于该点的度,此时把X中包含颜色的最小数目称为图G的集合点色数.文章应用构造染色函数法给出了两类广义-Mycielski图的集合点染色及其色数.     

Halin图的1-色数

Ｈａｌｉｎ图的１－色数为２的充要条件和１－色数为３的若干充分条件     

一类含有4-圈的单圈图一般点可区别全染色

设G为简单图.设f是图G的一个一般全染色,若对图G的任意两个不同的顶点u、v,有C(u)≠C(v),则称f为图G的一般点可区别全染色(简记为GVDTC).对图G进行一般点可区别全染色所需要的最少颜色数称为图G的一般点可区别全色数.将一类含有4-圈的单圈图悬挂边的染色按从小到大的顺序排列,探讨了它的一般点可区别全染色,确定了它具有一般点可区别全染色,并得到了它的一般点可区别全色数.     

图的条件色数的上界

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

mK的点可区别全染色mK的点可区别全染色

 利用色集事先分配法, 借助于矩阵构造具体染色及递归法的方法, 研究图的点可区别全染色问题, 给出了m个K4的点不交的并mK4的点可区别全色数χvt(mK4)的确切值, 即“如果k-14<4m≤k4, m≥2, k≥6, 则χvt(mK4)=k”. 验证了VDTC猜想对mK4成立.     

围长至少为5的平面图的线性着色

本文研究了围长至少为5的平面图的线性着色问题。利用反证法,通过分析最小反例图的结构,运用欧拉公式结合适当的权转移规则得出矛盾,从而证明了围长至少为5的平面图的线性色数满足lc(G)≤[△(G)/2]+4,改进了这方面的结果。     

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

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

一个特殊的双外平面图的全染色

双外平面图是一个平面图，它可以嵌入到平面上并使得它的顶点出现在两个面的边界上．设G是一个双外平面图，V(G)、E(G)、F(G)分别为双外平面图G的点集、边集和面集．G的全色数XT，(G)是使得V(G)∪E(G)中的任意相邻或相关联的两个元素均染不同颜色的最少颜色数．本文证明了最大度至少是6的2连通的特殊双外平面图G的全色数是△(G) 1，其中△(G)为G的最大度数．     

m个点不交的C4的并的点可区别全染色

给出了m（m≥2）个点不交的C4的并的点可区别全色数。     

图的强直积的2-距离染色

设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。     

m个点不交的C_4的并的点可区别全染色

给出了m(m≥2)个点不交的C4的并的点可区别全色数。