最大度为4的图的无圈列表边染色

对于图G=(V(G),E(G)),如果一个映射φ:E(G)→{1,2,…,k},使得G中任意相邻的两边e₁,e₂满足φ(e₁)≠φ(e₂),并且G中不含有双色圈,则称φ为G的一个无圈边染色.对于给定的列表分配L={L(e)|e∈E(G)},如果存在图G的一个无圈边染色φ,使得对于任意边e∈E(G),均有φ(e)∈L(e),则称染色φ为G的一个无圈L-边染色.如果对于任意的列表分配L,当对所有的边e∈E(G)满足|L(e)|≥k时,图G均存在无圈L-边染色,那么称G是无圈k-边可选的.使图G无圈k-边可选的最小的正整数k,称为G的无圈列表边色数,用a’_l(G)表示.本文证明了对于最大度△≤4的连通图G,如果|E(G)|≤2|V(G)|-1,则a’_l(G)≤6,扩展了Basavaraju和Chandran文[J.Graph Theory,2009,61(3):192-209]的结果.     

随机图的独立数和分数匹配数的一个注记（英文）

设I为图G顶点集的子集.如果I中的任意两个点均不相邻,则称I为G的独立集.G的最大独立集的阶数称为独立数,记为α(G).图G的分数匹配是边集上的函数f∈[0,1],使得对每个顶点v都有∑f(e)≤1,这里是对所有与顶点v相关联边的函数值求和.分数匹配数β(G)是所有的分数匹配f中∑₍e∈E(G))f(e)的最大值.本文给出了随机图上关于独立数α(G)与分数匹配数β(G)的一些结果.     

大围长图的广义无圈染色

图的顶点染色称为是r-无圈的,如果它是正常染色,使得每一个圈C上顶点的颜色数至少为min{|C|,r}.图G的r-无圈染色数是图G的r-无圈染色中所用的最少的颜色数.我们证明了对于任意的r≥4,最大度为△、围长至少为2(r-1)△的图G的r-无圈染色数至多为6(r-1)△.     

最大度为8不含特定子图的平面图的全染色

全染色是对图G的顶点和边同时进行正常染色,至少要用Δ+1个色才能对图G进行正常全染色.本文运用权转移的方法,证明了最大度为8的不含特定子图的简单平面图是9-全可染的.