特殊1-平面图的列表全染色

发布时间：2020-12-29 10:54

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

【文章来源】：山东大学山东省 211工程院校 985工程院校 教育部直属院校

【文章页数】：53 页

【学位级别】：硕士

【部分图文】：

图３．日情况２．４？雌；）＝３，ｃ（ｕ）?＝?３且有３个非Ｈ类源点??若｛ａ，／？，?７｝均为４－面，那么一定是这样的结构：化与３：２为同一点（记??

设叫２／矣Ｅ（ＧＸ），同理｛叫之，化２／｝中至少有一条边不在巧ＧＸ）中，设Ｍ２之餐??巧ＧＸ），?｛ｍ３２：，Ｍ３２｝中至少有一条边不在巧ＧＸ）中，不防设＂３＾?＾巧ＧＸ），??见［图３．５］，那么恤：咕：的｝均不是点的Ｈ类源点，由Ｒ２知点Ｕ从＂１，＂２，咕至??少得到Ｉ?Ｘ?３?＝?＾由Ｒ４知点Ｕ从其３－主点处得到＾所??ｃｈ＇｛ｖ）?＝?ｃｈ｛ｖ）?＋?＾?＋?＾?＝?０．??乙?Ｚｄ??若｛ａ，化７｝中至少存在一个５＋－面，由Ｒ８知点Ｕ从５＋－面至少得到！，由Ｒ４??知点Ｕ从其３－主点处得到＾所??ｃｈ！｛ｖ）?＝?ｃｈ｛ｖ）?＋?＾?＋?＾?＝?０．??么?么??情况３．?ｄ（Ｕ）二?４．??－２６－??

【参考文献】：
期刊论文
[1]不含3-圈的1-平面图的边染色[J]. 张欣,刘桂真,吴建良.  山东大学学报(理学版). 2010(06)
[2]Total colorings of planar graphs with maximum degree at least 8[J]. SHEN Lan & WANG YingQian College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua 321004, China.  Science in China(Series A:Mathematics). 2009(08)



本文编号：2945521