图的无圈染色

我们证明最大度Δ≥5的图的无圈色数至多是a(G)≤L(Δ-1)2/2」,这个结果比目前公认的最小上界a(G)=Δ(0-1)/2要小。同时得出两个新的结论:对任意Δ=5的图G,有a(G)≤8;对任意Δ=6的图G,有a(G)≤12。     

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

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

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

令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。     

点可区别边色数和点可区别全色数的两个上界

应用概率方法中的第一矩量原理和Markov不等式,证明了对于最大度为Δ的n阶图G,当Δ≥2时,其点可区别的边色数χv′d(G)≤nΔ(n-1),当n≥3,Δ≥1时,其点可区别的全色数χvt(G)≤2 nΔ(n-1).     

图的星色数的两个结果

图G的星染色是图G的正常点染色,使得图G中没有长为3的路2-染色.通过应用概率方法中的非对称局部引理,证明了任一最大度为Δ的图的星色数χs(G)≤48Δ3.通过应用第一矩量原理和Markov不等式,证明了对任一有n个顶点的最大度为Δ的图G,其星色数χs(G)≤nΔ.     

Δ(G)=3的图的列表-L(2,1)-标号

记Δ(G)和λl(G)分别为图G的最大度和列表-L(2,1)-标号数.若Δ(G)≤3,则称G为子三次图.证明了若G是子三次图,那么λl(G)≤12;若G为最大平均度Mad(G)8/3的子三次图,那么λl(G)≤10.这一结果进一步支撑了Griggs和Yeh关于距离2标号的猜想.     

稀疏图平方图的染色数上界

图G的平方G2定义为顶点集V(G)=V(G²), 并且uv∈E(G²)当且仅当u和v之间的距离至多为2. G²的色数χ(G²)是指使得G²存在正常k顶点染色的最小整数k. 用权转移的方法证明: 如果mad(G)<4且Δ(G)≥7, 则χ(G²)≤3Δ(G)+1;  如果mad(G)≤4且Δ(G)≥8, 则χ(G²)≤3Δ(G)+5.     

边色数分类的两个充要条件及其性质

设图 G 是简单连通图,由 Vizing 定理知:Δ(G)≤x′(G)≤Δ(G)+1.其中Δ(G)表示图 G 的最大顶点次,x′(G)是图 G 的边色数.若 x′(G)=Δ(G),则称 G 为第一类图,并简记为 G∈C~1;若 x′(G)=Δ(G)+1,则称 G 为第二类图,并简记为 G∈C~2.其他图论述语见一般教科书。如果 G 满足|E(G)|>Δ(G)[(|V(G)/2|)],则称 G 为满图。显然,若图 G 为满图,则     

最大平均度不超过4的图的线性2-荫度

一个2-线性森林是指每个分支均为长至多为2的路的图。将图G的边集合划分为m个线性2-森林的最小整数m,称为图G的线性2-荫度,记作la_2(G)。确定了mad(G)≤4的图的线性2-荫度的上界,若图G为mad(G)≤4的图,则la_2(G)≤「Δ(G)/2」+5(Δ(G)≡1,2(mod4));la2(G)≤「Δ(G)/2」+4(Δ(G)≡0,3(mod4))。     

一个简单图的正则包装问题

本文的主要结果是定理对简单图G,必有Δ正则的简单图G,使得G?G,且v(G)≤v(G) Δ 2,其中Δ=Δ(G).进而,还论述了作为一般结论,这个定理中所给出的界是最佳结果.