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

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

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

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