關(guān)于1-平面圖的若干列表染色的問題研究.pdf

1、圖G的染色問題是圖論的主要研究?jī)?nèi)容,本文就圖的1-平面圖的列表邊染色和列表全染色作了一些研究。
　　一個(gè)圖G稱為是1-平面的當(dāng)且僅當(dāng)它可以畫在一個(gè)平面上,使得它的任何一條邊最多交叉另外一條邊。稱L映射為圖G的一個(gè)全列表分配,如果它給每一個(gè)元素x∈V∪E一個(gè)顏色集合L(x);若有一個(gè)正常全染色c,使得每一個(gè)元素x滿足c(x)∈L(x),則稱G是-全可選的,或稱c是G的一個(gè)L全染色;若對(duì)任意的分配L和x∈V∪E,都有L(x)≥k,且G

2、是L全可選的,則稱G是k-全可選的。G的全列表色數(shù)χl′(G)是使得G是k-全可選的最小的整數(shù)k.類似地,可定義G邊列表色數(shù)χl′(G)。
　　本文主要根據(jù)圖的結(jié)構(gòu)和性質(zhì),利用差值轉(zhuǎn)移法等方法對(duì)1-平面圖的列表邊數(shù)和列表全染色下界的進(jìn)行研究,得到并證明了如下結(jié)果:
　　本文第1章對(duì)圖論的歷史、基本概念和本文的研究背景作了簡(jiǎn)單介紹。
　　本文第2章主要證明了不含相鄰3-圈的1-平面圖的列表邊染色和列表全染色的相關(guān)結(jié)果:<

3、br>　　(1)若G是≥17的1-平面圖,則G是-邊可選的,(+1)-全可選的。
　　(2)若G是≥13的1-平面圖,則G是(+1)-邊可選的,(+2)-全可選的。
　　本文第3章主要證明了不含相鄰4-圈的1-平面圖的列表邊染色和列表全染色的相關(guān)結(jié)果:
　　(1)若G是≥19的1-平面圖,則G是邊可選的,(+1)-全可選的。
　　(2)若G是≥13的1-平面圖,則G是(+1)-邊可選的,(+2)-全可選的。