论文部分内容阅读
本文所研究的图为简单的、有限的、无向的、非空连通图。一个图称为是1-平面图如果它可以画在平面上且使得每条边至多交叉另外一条边。对于1-平面图,本文假设G已经嵌入到平面上且满足: (a)每条边至多交叉一次; (b)交叉点的数目最小。 图的列表染色是一种特殊的染色方式。设映射L给每个元素α∈V∪E分配一个颜色集合L(α),则称L是图G的一个全列表分配。如果存在一个正常全染色c,使得对每一个元素α∈V∪E都有c(α)∈L(α),则称G是L-全可选的,或L-列表全可染的。如果对任意满足|L(x)|≥k的列表分配L,其中x∈V∪E,都有G是L-全可选的,则称G是k-全可选的,或k-列表全可染的。我们用x"l(G)表示G的列表全色数,指的是使得G是k-全可选的最小整数k。 本文根据1-平面图G及其关联平面图G(x)的结构性质,利用权转移的方法证明特殊的1-平面图,即无交叉3-圈的1-平面图和无交叉3,4-圈的1-平面图的列表全染色问题。文章主要内容如下: 第一章介绍了文章的基本定义和研究背景; 第二章证明定理1:对于无交叉3-圈的1-平面图G,当△≥16时,是(△+1)-列表全可染的,即x"l(G)=△+1。 第三章证明定理2:对于无交叉3,4-圈的1-平面图G,当△≥14时,是(△+1)-列表全可染的,即当1-平面图G的每个点至多关联一个3-圈或4-圈且△≥14时,x"l(G)=△+1.