平面圖的全可選和3-染色.pdf

1、用G=(V,E)表示頂點(diǎn)集為V,邊集為E的圖,而圖的面集,最大度,最小度分別用F,△,δ表示.若V∪ E中的元素能用k種顏色進(jìn)行染色,使得任意兩個(gè)相鄰或相關(guān)聯(lián)的元素染有不同的顏色,則稱G是K-全可染的.圖G的一個(gè)全色列表是一個(gè)顏色集合簇L,對(duì)G的每個(gè)元素x∈V ∪ E都配一個(gè)顏色集合L(x).若對(duì)每一個(gè)滿足｜L(x)｜=k,x∈V∪ E的L,G都是L-全可染的,則稱G是k-全可選的.圖G的一個(gè)正常k-頂點(diǎn)染色是指一個(gè)映射φ:V→{1,…

2、,k},使得對(duì)任意uv∈E(G),滿足φ(u)≠φ(v).
　　 關(guān)于圖的全可選和邊可選,有以下著名的猜想(List Coloring Conjecture):對(duì)任意圖G,(a))x'l(G)=x'(G)；(b)x"l(G)=x"(G).猜想主要由Vizing和Borodin等人獨(dú)立提出.關(guān)于平面圖的3-染色問題,最著名的是Steinberg猜想:不含4,5-圈的平面圖是3-可染的.人們的一系列研究主要圍繞這兩個(gè)問題展開,通過多

3、年研究人員的不斷改進(jìn),現(xiàn)已有一定的進(jìn)展.
　　 本文在前人的工作基礎(chǔ)上,圍繞上述猜想和問題,在平面圖的全可選中,主要運(yùn)用Discharging方法證明了:
　　 (1)△≥8且不含相交三角形的平面圖G是(△+1)-全可選的；
　　 (2)△≥9且不含相鄰三角形的平面圖G是(△+1)-全可選的.
　　 在平面圖的3-染色中,運(yùn)用延拓性引理,壞圈,新好路的定義和Discharging等方法,證明了: