稀疏图的(0,1)-松弛强边着色

给定一个图G=(V(G),E(G)),图G的(s,t)-松弛强边着色数是指使得图G有(s,t)-松弛强k边着色的最小k值,记作χ′(s,t)(G).证明了在图G中,如果mad(G)<3,Δ≤7,那么χ′(0,1)(G)≤3Δ-1;同时证明了对于任意一个平面图G,如果g(G)≥7,Δ≥4,那么χ′(0,1)(G)≤[5△/2]     

平面图的平方染色数的一个新上界

令V(G)、E(G)、Δ(G)和χ(G)分别为G的顶点集、边集、最大度和色数。图G的平方图,记为G2,指的是一个图满足条件:V(G2)=V(G),并且uv∈E(G2)当且仅当1≤dG(u,v)≤2。证明了若G是Δ(G)≤6且围长g(G)≥5的平面图,则χ(G2)≤Δ(G)+8。     

围长至少为6的曲面图的列表单射染色

图G的一个点染色称为单射染色,如果任何两个有公共邻点的顶点染不同的颜色.一个图G称为单射k-可选择的,如果对于顶点V(G)的任何一个大小为k的允许颜色列表L,都存在一个单射染色φ,使得对于v∈V(G),有φ(v)∈L(v).使得G为单射k-可选择的最小k,称为G的列表单射染色数,记作χ_i~l(G).设G是最大度为Δ,围长为g的可嵌入到欧拉示性数χ(Σ)≥0的曲面Σ的一个图.证明了若Δ≥7且g≥6,则χ_i~l(G)≤Δ+3.     

利用图的圈秩数进行边色数的分类

本文利用最大次顶点的导出子图的圈秩数研究了边色数的分类,得到下面的结果:定理1 设 G 为简单连通图,G_Δ为连通图,G_Δ的圈秩为 l,Δ(G_Δ)≤3,δ(G_Δ)≤2,Δ(G)≥1/2(|V (G)|+3l+1)+2l-1.则 G∈C~2G 含有满子图H,Δ(H)=Δ(G).     

弱直积图的2-距离色数

图G(V,E)的2-距离染色是指正常的顶点染色,且任意距离不大于2的两个顶点着不同的颜色.得到弱直积图的一个2-距离色数的可达界,即Δ(G).Δ(H)+1≤χ2(G×H)≤χ2(G).2χ(H),且给出一些特殊弱直积图的2-距离色数,说明此界可达.如χ2(P2×Pn)=Δ(P2).Δ(Pn)+1=3(n≥3),χ2(Pm×Pn)=Δ(Pm).Δ(Pn)+1=5(m≥3,n≥3)说明下界可达,χ2(Km×Kn)=χ2(Km).2χ(Kn)=mn,说明上界可达.     

最大度为5的简单图的2-距离列表染色

通过对极小反例G的结构分析,利用权转移的方法,证明了:对于Δ(G)≤5的图G,若mad(G)20/7,则χl2(G)≤10;若mad(G)19/6,则χl2(G)≤11.这一结果改进了现有的部分结论.     

2-连通外部平面图的平方图的列表染色

图G的平方图,记作G2,是一个以原图的顶点集作为顶点集,若原图中两点的距离不大于2则连以边所成的图.图G的列表染色数,记作lχ(G),定义为最小的自然数k,使得满足:对任一顶点给定k种颜色的列表,且染色时每个顶点的颜色只能从自身的颜色列表中选择时,总存在G顶点的一个正常染色.设G是一个最大度为Δ(G)的2-连通外部平面图,则lχ(G2)≤Δ(G)+2.     

有低最大平均度的图的(2,1)-全标号

图G的最大平均度mad(G)是其所有真子图的平均度的最大值,即mad(G)=max{(2|E(H)|)/(|V(H)|)},H■G.文中证明了:若G为连通图,△(G)≤3,mad(G)9/4,则λ_2~T(G)≤5.若G为连通图,△(G)≤4,mad(G)5/2,则λ_2~T(G)≤7.     

图中具有指定性质的独立4-圈

主要给出了图G恰好含有s个K3和k-s个K4的最小度条件即:设G是一个简单图,s,k是两个正整数且s k,其中G的顶点个数n≥3s+4(k-s)+3,如果G中任意两个不相邻顶点的最小度之和σ2(G)≥4n-3s-8/|2|或者最小度δ(G)≥3n+2k-s-2/4,则G包含k个顶点不相交的圈C1,C2…Ck,并且Ci=K3其中1≤i≤s,Cj=K4其中sj≤k.     

图的独立数与分数一致性

设G是一个顶点集为V(G),最小度为δ(G),独立数为α(G)的图,k≥2是整数。图G的支撑子图F称作是图G的分数k-因子,如果对于每一个x∈V(F)都有dh G(x)=k。如果对于图G的每条边e,图G都有一个分数k-因子包含它而且同时有一个分数k-因子不包含它,则称图G为分数k一致图。证明了如果δ(G)≥k+2,且α(G)≤4k(δ-k-1)/(k+1)2,则图G是一个分数k一致图。     

图的某些[r,s,t]-染色的色数

证明了(1)若图G是二部图,则当r≥s(χ’(G)-1)+2时,χr,s,1(G)=χr,0,0(G);(2)若图G是非二部图,则当r≥sχ’(G)/χ(G)-s+1且r不是s的倍数时,χr,s,1(G)=χr,0,0(G);(3)当Δ(G)≥2,χ’(G)=Δ(G),且s≥2r,r≥2t时,χr,s,t(G)=χ0,s,0(G);(4)当χ’(G)=Δ(G)+1且s-t≥r≥t时,χr,s,t(G)=χ0,s,0(G)。     

联图 Ws∨Km,n的邻点可区别全色数

图的邻点可区别全染色(AVDTC)数为χ_at(G)，有猜想：x_at(G)≤Δ(G)+3. 联图 W_s∨K_{m,n的邻点可区别全色数被确定为χat(Ws∨Km,n)=Δ( Ws∨Km,n)+1或Δ(Ws∨Km,n)+2.}     

图的星边星-全色数的一个上界

提出图的星边星-全染色的概念,图G的一个正常全染色被称为星边星-全染色,如果对G中点进行星染色,边进行星边染色.并定义图的星边星-全色数,记为χsTs(G).用构造染色的方法给出一些特殊图(路,圈,轮,扇,完全图)的星边星-全色数.同时运用概率方法给出满足一定条件的图G的星边星-全色数的一个上界,即若图G的最大度Δ(G)≥30,则χsTs(G)≤24(Δ-1)3/2.     

平面图的无圈边染色

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

点关联较少3-面的平面图的全染色

证明了对每点至多关联2个3-面的平面图，全染色猜想成立. 对每点至多关联2个3-面且Δ(G)≥8的平面图，有x_T(G)=Δ(G)+1.对每点至多关联[Δ(G)/2」个3-面且Δ(G)≥9的平面图，有x_T(G)=Δ(G)+1.     

不含相交5-圈的平面图的线性2-荫度

设G是不含相交5-圈的平面图,证明了如果G是连通的并且δ(G)≥2,则G包含一条边xy,使得d(x)+d(y)≤10或者一个2-交错圈。由这个结果可以得到G的线性2-荫度la₂(G)≤「Δ/2+5,改进了不含5-圈的平面图的线性2-荫度的已知上界。     

超环面图上的约束数

非空图G的约束数b(G)是指使得图G的控制数γ(G)增大而删除的最少的边数.[Fischermann M, Rautenbach D, Volkmann L. Remarks on the bondage number of planar graphs. Discrete Math,2003,260:57-67\]已经证明,对于一个围长为g(G)的平面图G,如果g(G)≥4则b(G)≤6,如果g(G)≥5则b(G)≤5,如果g(G)≥6则b(G)≤4,如果g(G)≥8则b(G)≤3.我们把这个结果推广到连通的超环面图中.     

高度图的全色数

证明了：如果图G的最大度顶点数r(G）满足r(G)≥|V（G）|-△（G）-1,且δ（G） 2△（G）≥5/2|V（G）| 3/2,则G的全色数xT(G)=△（G） 1。