围长至少为21的平面图的邻和可区分的顶点列表色数

设f是从图G的顶点集合V到整数集合N的一个映射,令每一个点v的邻和为S_f(v)=Σ_(u∈NG(v))f(u),若f满足任意相邻两点的邻和不相等,则称f是图G的一个邻和可区分的顶点列表标号。设L为图G的一个k-列表配置,对任意点v有f(v)∈L(v)。若存在最小的正整数k使得对任意L,图G都有一个邻和可区分的顶点列表标号f,则称k为图G的邻和可区分的顶点列表色数,η_l(G)。证明当平面图G的围长至少为21时,图G的邻和可区分的顶点列表色数η_l(G)至多为3。

最大度为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的围长.

Halin图的Alon-Tarsi数

图G的Alon-Tarsi数,是指最小的k使得G存在一个最大出度不大于k-1的定向D满足G的奇支撑欧拉子图的个数不同于偶支撑欧拉子图的个数.通过分析Halin图的结构,利用Alon-Tarsi定向的方法确定了Halin图的Alon-Tarsi数.

图的列表着色

本文围绕列表着色展开讨论,将列表着色方面的已有结论进行了整理和简要的证明及补充说明.本文对一些猜想的特殊情况进行了论证.

系列-平行图的列表染色

系列 -平行图是没有子图与K4同胚的图 .设G为一个系列 -平行图 .如果对任意的边e∈E(G) ,有 f(e) ≥max{ 4,Δ(G) } 则G是f 可列表染色的 .同时还确定了所有系列 -平行图的边色数 .

含相邻三角形的平面图的列表边和列表全染色

给定一个平面图G,χ′l(G)和χ″l(G)分别表示图G的列表边色数和列表全色数。证明了:如果一个平面图G满足Δ(G)≥7,并且任何一个三角形至多和一个其他的三角形相邻,则有χ′l(G)≤Δ(G)+1和χ″l(G)≤Δ(G)+2成立。