平面圖的全可染和全可選.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作 者 盧秋麗指導(dǎo)教師 王墮萱學(xué)位類(lèi)別 理學(xué)碩士學(xué)科專(zhuān)業(yè) 運(yùn)籌學(xué)與控制論學(xué)位授予單位 浙江師范大學(xué)論文答辯日期 2 0 1 2 年5 月2 7 日平面圖的全可染和全可選摘要給定一個(gè)平面圖G = ( V 目，它的項(xiàng)點(diǎn)集．邊集，而集，

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

3、 ∈V u E 的L 圖G 都是L 一全可染的，則稱(chēng)圈G 是☆一全可選的對(duì)于圖的全染色，早在2 0 世紀(jì)6 0 年代．V i z i n g 和B e h z a d 就分別獨(dú)立的提卅了全染色猜想：任意的簡(jiǎn)甲圖G 都是f △+ 2 ) 一全可染的到目前為止，只有△= 6 的平面圖是否是8 一全可染的問(wèn)題尚未解決關(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 ) ：對(duì)任意圖G ，( a ) 以( G ) = ×’( G ) ：( b )訂( G ) = x ”( G )本文在前人的工作基礎(chǔ)卜，圍繞著卜述猜想和問(wèn)題，在平面圖的全可染和全可選中．主要運(yùn)用D i s c h a r g i n g 方法證明了( 1 ) 3 + 圈和6 - 圈不相鄰的平面圖G 是( △+ 2 ) 一全可染的( 2 ) △2 7 且不含相鄰4 - 圈的平面圖G 是( △+ 1 ) 一全可選的，·