平面圖的全可染和全可選.pdf

1、平面圖的全可染和全可選T o t a l C o l o r i n g sa n d L i s tT o t a l C o l o r i n g s o fP l a n a r G r a p h s作 者 盧秋麗指導教師 王墮萱學位類別 理學碩士學科專業(yè) 運籌學與控制論學位授予單位 浙江師范大學論文答辯日期 2 0 1 2 年5 月2 7 日平面圖的全可染和全可選摘要給定一個平面圖G = ( V 目，它的項點集．邊集，而集，

2、最大度和最小度分別用v ，E ，F(xiàn) ，△和J 表示若y u E 中的元素能夠用女種顏色進行染色，使得任意兩個相鄰或相關(guān)聯(lián)的元素都染有不同的顏色．則稱圖G 有一個正常的t 一全染色，也稱圖G 是女一全可染的使得圖G 是正常k 一全染色的最小的正整數(shù)☆叫做圖G的全色數(shù)顯然．全色數(shù)至少為△+ l 圖G 的一個全色列表是一個顏色集合簇￡，對圖G 中的每個元素z ∈V u F 都配有一個顏色集合L ( z ) 若對每一個滿足L 扣) = k ，z

3、 ∈V u E 的L 圖G 都是L 一全可染的，則稱圈G 是☆一全可選的對于圖的全染色，早在2 0 世紀6 0 年代．V i z i n g 和B e h z a d 就分別獨立的提卅了全染色猜想：任意的簡甲圖G 都是f △+ 2 ) 一全可染的到目前為止，只有△= 6 的平面圖是否是8 一全可染的問題尚未解決關(guān)于圖的全可選和邊可選，有以下著名的猜想( L i s t C o l o r i n g C o n j e c t u r

4、e ) ：對任意圖G ，( a ) 以( G ) = ×’( G ) ：( b )訂( G ) = x ”( G )本文在前人的工作基礎(chǔ)卜，圍繞著卜述猜想和問題，在平面圖的全可染和全可選中．主要運用D i s c h a r g i n g 方法證明了( 1 ) 3 + 圈和6 - 圈不相鄰的平面圖G 是( △+ 2 ) 一全可染的( 2 ) △2 7 且不含相鄰4 - 圈的平面圖G 是( △+ 1 ) 一全可選的，·