本文所研究的圖為簡單的、有限的、無向的、非空連通圖。一個圖稱為是1-平面圖如果它可以畫在平面上且使得每條邊至多交叉另外一條邊。對于1-平面圖,本文假設(shè)G已經(jīng)嵌入到平面上且滿足：（a）每條邊至多交叉一次；（b）交叉點的數(shù)目最小圖的列表染色是一種特殊的染色方式。設(shè)映射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的列表全色數(shù),指的是使得G是κ-全可選的最小整數(shù)k。本文根據(jù)1-平面圖G及其關(guān)聯(lián)平面圖G×的結(jié)構(gòu)性質(zhì),利用權(quán)轉(zhuǎn)移的方法證明特殊的1-平面圖,即無交叉3-圈的1-平面圖和無交叉3,4-圈的1-平面圖的列表全染色問題。文章主要內(nèi)容如下：第一章介紹了文章的基本定義和研究背景；第二章證明定理1：對于無交叉3-圈的1-平面圖G,當(dāng)△≥16時,是（△+1）-列表全可染的,即χl"（G）=△+1... 

【文章來源】：山東大學(xué)山東省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：53 頁

【學(xué)位級別】：碩士

【部分圖文】：

圖３．日情況２．４？雌；）＝３，ｃ（ｕ）?＝?３且有３個非Ｈ類源點??若｛ａ，／？，?７｝均為４－面，那么一定是這樣的結(jié)構(gòu)：化與３：２為同一點（記??

設(shè)叫２／矣Ｅ（ＧＸ），同理｛叫之，化２／｝中至少有一條邊不在巧ＧＸ）中，設(shè)Ｍ２之餐??巧ＧＸ），?｛ｍ３２：，Ｍ３２｝中至少有一條邊不在巧ＧＸ）中，不防設(shè)＂３＾?＾巧ＧＸ），??見［圖３．５］，那么恤：咕：的｝均不是點的Ｈ類源點，由Ｒ２知點Ｕ從＂１，＂２，咕至??少得到Ｉ?Ｘ?３?＝?＾由Ｒ４知點Ｕ從其３－主點處得到＾所??ｃｈ＇｛ｖ）?＝?ｃｈ｛ｖ）?＋?＾?＋?＾?＝?０．??乙?Ｚｄ??若｛ａ，化７｝中至少存在一個５＋－面，由Ｒ８知點Ｕ從５＋－面至少得到！，由Ｒ４??知點Ｕ從其３－主點處得到＾所??ｃｈ�。觯�?＝?ｃｈ｛ｖ）?＋?＾?＋?＾?＝?０．??么?么??情況３．?ｄ（Ｕ）二?４．??－２６－??

【參考文獻(xiàn)】：
期刊論文
[1]不含3-圈的1-平面圖的邊染色[J]. 張欣,劉桂真,吳建良.  山東大學(xué)學(xué)報(理學(xué)版). 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