（應(yīng)用數(shù)學(xué)專業(yè)論文）平面圖的3染色.pdf

i i i l i j l l l l l l l l l l l l l l l i l l l l i l l l l l l l l u l l l l r l l l l i h i y 18 0 4 3 3 8 圖g 的一個(gè)正常k 頂點(diǎn)染 e ( g ) ，滿足( u ) ( ) 若圖g 有一個(gè)正常尼頂點(diǎn)染色，那么就稱圖g 是尼頂點(diǎn)可染色的( 簡(jiǎn)稱七一可染色 的) 若圖g 可以嵌入到平面內(nèi)使得邊僅在端點(diǎn)處相交，則說(shuō)g 是一個(gè)可平面圖 可平面圖在平面內(nèi)的任何一個(gè)具體的使得邊僅在端點(diǎn)處相交的嵌入q 做平面圖 1 9 5 9 年，g r b t z s c h 證明了每一個(gè)不含三角形的平面圖是3 可染色的1 9 7 6 年， s t e i n b e r g 猜想：不含4 ，5 一圈的平面圖是3 一可染色的圍繞s t e i n b e r g 猜想，人們展 開了一系列的研究e r d b s 建議去研究如下更弱的問題：是否存在常數(shù)k ，使得不 含4 至k 圈的平面圖是3 可染的? 1 9 9 1 年，a b b o t t 和z h o u 證明了這樣的k 是存 在的，且k 1 1 接著，b o r o d i n ，s a n d e r s 和z h a o 分別獨(dú)立地證明了k 9 后來(lái)， b o r o d i n 等人進(jìn)一步改進(jìn)到南7 ，即證明了不含4 ，5 ，6 ，7 圈的平面圖是3 一可染色 的本文從不含相鄰短圈的角度考慮平面圖的3 染色，運(yùn)用延拓性引理和粘點(diǎn)收 縮面等方法，在第二章證明了7 一圈不相鄰的平面圖是3 一可染色的顯然該結(jié)果 改進(jìn)了b o r o d i n 等人所得的上述結(jié)論 作為對(duì)s t e i n b e r g 猜想更進(jìn)一步的研究，許寶剛于2 0 0 6 年證明了不含5 ，7 圈且 不含相鄰三角形的平面圖是3 可染色的但是b o r o d i n 等人在2 0 0 9 年找到了該文 證明當(dāng)中的反例( 許寶剛后來(lái)對(duì)自己的證明作了修正) ，并給出了該結(jié)論新的證明 本文在第三章給出了這一結(jié)論的新的證明 本文在第四章證明了：不含6 ，8 圈，且3 圈不與3 ，4 一圈相鄰，4 圈不與5 圈 相鄰的平面圖是3 一可染色的該結(jié)果進(jìn)一步改進(jìn)了王維凡和陳敏的一個(gè)工作：不 含4 ，6 ，8 一圈的平面圖是3 可染色的這一結(jié)論 i 關(guān)鍵詞：平面圖；3 染色；圈；可延拓性 t h r e e c o l o r a b i l i t y0 f p l a n a rg r a p h s a b s t r a c t l e tg = ( v e ) b eag r a p hw i t ht h es e to f v e r t i c e sva n dt h es e to f e d g e se a m a p p i n g ：v _ 1 ，七) i sc a l l e dak - c o l o r i n go fgi f 矽( u ) ( 口) w h e n e v e r t v e i fga d m i t sa k - c o l o r i n g ，t h e ng i ss a i dt ob ek - c o l o r a b l e c a l la g r a p hp l a n a r i fi tc a nb ee m b e d d e di n t ot h ep l a n es ot h a ti t se d g e sm e e to n l ya tt h e i re n d s ；s u c ha p a r t i c u l a re m b e d d i n go fap l a n a rg r a p hi sc a l l e dap l a n eg r a p h i n19 5 9 ，g r f t z s c hp r o v e dt h a tp l a n a rg r a p h sw i t h o u t 3 - c y c l e sa r e3 - c o l o r a b l e i n 19 7 6 ，s t e i n b e r gc o n j e c t u r e de v e r yp l a n a rg r a p hw i t h o u t4a n d5 - c y c l e si s3 - c o l o r a b l e p e o p l eh a v ed o n ea s e r i a lo f r e s e a r c ho ns t e i n b e r gc o n j e c t u r e i n1 9 9 3 ，e r d 6 ss u g g e s t e d t os t u d yaw e a kf o r mo ft h i sp r o b l e m ，a s k i n gi ft h e r ee x i s t sa ni n t e g e rks u c ht h a te v e r y p l a n a rg r a p hw i t h o u tc y c l e so fl e n g t hf r o m4t oki s3 - c o l o r a b l e a b b o t ta n dz h o u ( 1 9 9 1 ) p r o v e dt h a ts u c hake x i s t sa n dk 1 1 t h i sr e s u l tw a sl a t e ri m p r o v e dt o 尼9b yb o r o d i n ( 19 9 6 ) a n d ，i n d e p e n d e n t l y ，s a n d e r sa n dz h a o ( 1 9 9 5 ) ，a n dt ok 7 b yb o r o d i ne ta 1 ( 2 0 0 5 ) t h e s ep r o v et h a te v e r yp l a n a rg r a p hw i t h o u t4 ，5 ，6o r7 c y c l ei s3 - c o l o r a b l e i nc h a p t e r2 ，w ec o n s i d e rt h e3 - c o l o r i n go fp l a n a rg r a p h sw i t h o u t a d j a c e n tc y c l e s ，a n dp r o v et h a tp l a n a rg r a p h sw i t h o u ta d j a c e n t7 - - c y c l e sa r e3 - c o l o r a b l e b ye x t e n d a b i l i t yl e m m a sa n di d e n t i f i c a t i o n o b v i o u s l y , i ti m p r o v e st h er e s u l to b t a i n e d b yb o r o d i ne ta 1 ( 2 0 0 5 ) a saf u r t h e rs t u d yo f s t e i n b e r gc o n j e c t u r e ，i n2 0 0 6 ，x up r o v e dt h a tp l a n a rg r a p h s w i t h o u t5a n d7 - c y c l e sa n dw i t h o u ta d j a c e n tt r i a n g l e sa r e3 - c o l o r a b l e i n2 0 0 9 ，b o r o d i n e ta 1 f o u n da c o u n t e r e x a m p l eo ft h er e s u l to fx u ( x u h a sd o n eac o r r e c t i o no fh i sp r o o f l a t e r ) ，a n dg a v ean e wp r o o f i nc h a p t e r3o ft h i sp a p e r , w et h i n ko fo t h e rw a y st op r o v e t h es a m er e s u l t i i i i nc h a p t e r4 ，w ep r o v e ：p l a n a rg r a p h sw i t h o u t6a n d8 - c y c l e s ，a n d3 - c y c l e sn o t a d j a c e n tt o3o r4 - c y c l e s ，a n d4 - c y c l e sn o ta d j a c e n tt o5 - c y c l e sa r e3 - c o l o r a b l e t h i s r e s u l ti m p r o v ear e s u l tb yw a n ga n dc h e n ：p l a n a rg r a p h sw i t h o u t4 ，6 ，8 - c y c l e sa r e 3 一c o l o r a b l e k e yw o r d s ：p l a n a r g r a p h s ；3 - c o l o r i n g ；c y c l e s ；e x t e n d a b i l i t y i v j，氈wlt二ljl111， 目錄 摘要 i a b s t r a c t i i i 目錄：v 1 緒論 1 1 1 基本概念1 1 23 一可染色問題的研究概況 2 1 3 本文的主要結(jié)果4 2 沒有相鄰短圈的平面圖的3 染色 6 2 1 延拓性引理6 2 2 定理2 1 的證明1 1 3 不含5 ，7 一圈的平面圖的3 染色1 2 3 1 延拓性引理1 2 3 2 定理3 1 的證明2 l 4 不含6 ，8 圈的平面圖的3 。染色2 7 4 1 延拓性引理2 7 4 2 定理4 1 的證明3 2 參考文獻(xiàn)3 3 在學(xué)期間的研究成果及發(fā)表的論文3 6 致謝3 7 浙江師范大學(xué)學(xué)位論文獨(dú)創(chuàng)性聲明3 8 學(xué)位論文使用授權(quán)聲明3 8 浙江師范大學(xué)學(xué)位論文誠(chéng)信承諾書3 9 v v i 1 1 基本概念 1 緒論 在本節(jié)中，我們定義一些本學(xué)位論文中要用到的圖論的基本術(shù)語(yǔ)與符號(hào) 一個(gè)有序?qū) = ( ke ) 稱為一個(gè)無(wú)向圖，其中y 是一個(gè)有限集合，e 是y 中的不同元素的無(wú)序?qū)Φ募蟳 中的元素叫做圖g 的頂點(diǎn)，e 中的元素叫做圖 的邊通常用y ( g ) ，e ( g ) 分別表示圖g 的頂點(diǎn)集合與邊集合沒有重邊和環(huán)的 圖叫做簡(jiǎn)單圖除非特別指出，本文研究的圖均指有限簡(jiǎn)單無(wú)向圖 常用u ，u 表示g 中的點(diǎn)，e 表示g 中的邊若邊e = u v e ( g ) ，則說(shuō)釷，口在 g 中相鄰；這時(shí)又說(shuō)“和鈔是e 的端點(diǎn)，也說(shuō)u ，“與e 相關(guān)聯(lián)設(shè) 是一個(gè)頂點(diǎn)， 的全體鄰點(diǎn)所形成的集合口q 做u 的鄰域i 記作( 口) 與v 相關(guān)聯(lián)的邊的條數(shù)叫做 u 的度數(shù)，記作c f ( 穢) g 中的點(diǎn)的最小和最大的度數(shù)分別記作6 ( g ) 和( g ) 若 d ( v ) = k ( d ( v ) k ，d ( v ) 七) ，則稱v 為一個(gè)七點(diǎn)( 擴(kuò)點(diǎn)，k - 點(diǎn)) g 中長(zhǎng)度為k 的圈稱為七圈用k - _ 圈和忌+ 圈分別表示長(zhǎng)度至多和至少是k 的圈特別，把長(zhǎng) 度為3 的圈叫做三角形常用i c i 表示圈c 的長(zhǎng)度若兩個(gè)圈至少有一條公共邊， 則稱這兩個(gè)圈相鄰如果兩個(gè)相鄰的圈恰好有兩個(gè)公共點(diǎn)，那么稱這兩個(gè)圈是正 規(guī)相鄰的，顯然這兩個(gè)公共點(diǎn)是相鄰的 如果圖g 可以嵌入到平面上使得邊僅在端點(diǎn)處相交，則說(shuō)g 是一個(gè)可平面 圖可平面圖在平面內(nèi)的任何一個(gè)具體的使得邊僅在端點(diǎn)處相交的嵌入叫做平 面圖設(shè)圖g 是平面圖，常用f ( g ) 表示面集合對(duì)于廠f ( g ) ，用b ( i ) 表示圍 繞面，的閉途徑把途徑b ( f ) 的長(zhǎng)度稱為面，的度( 每條割邊被計(jì)算兩次) ，記為 d ( 廠) 若d ( f ) = k ( d ( f ) k ，d ( f ) 忍) ，則稱，為一個(gè)七面( 礦一面，k - _ 面) 若頂 點(diǎn)u ( 邊e ) 在面廠的邊界上，則說(shuō)v ( e ) 與，在g 中相關(guān)聯(lián)若兩個(gè)面至少有一條 公共邊，則稱這兩個(gè)面相鄰如果兩個(gè)相鄰的面恰好有兩個(gè)公共點(diǎn)，那么稱這兩個(gè) 面是正規(guī)相鄰的若一個(gè)面的邊界是一個(gè)圈，則稱這個(gè)面是一個(gè)簡(jiǎn)單面若平面圖 l 1 緒論 g 是2 。連通的，則它的每個(gè)面的邊界都是一個(gè)圈，常用這個(gè)圈的項(xiàng)點(diǎn)序列來(lái)表示 這個(gè)面 設(shè)g 7 = ( v 7 ，e 7 ) g = ( ee ) ，若g 中的端點(diǎn)屬于y 7 中的邊全在e 7 中， 則稱g 7 = ( v 7 ，e 7 ) 為g 的一個(gè)點(diǎn)導(dǎo)出子圖，記作c v ，】設(shè)c 是g 中的一個(gè) 圈，用i n t ( c ) ( e x t ( c ) ) 表示嚴(yán)格在c 內(nèi)部( 外部) 的點(diǎn)集如果i n t ( c ) 和e z t ( c ) 都非空，則把g 叫做分離圈；否則，叫做面圈顯然，i n t ( c ) = g e x t ( c ) 和 e x t ( c ) = g i n t ( c ) 是g 的兩個(gè)點(diǎn)導(dǎo)出子圖 ， 圖g 的一個(gè)正常尼一頂點(diǎn)染色是指一個(gè)映射：v _ 1 ，七) ，使得對(duì)任意 讓口e ( g ) ，滿足( 讓) ( 口) 若圖g 有一個(gè)正常后一頂點(diǎn)染色，那么就稱圖g 是 七一頂點(diǎn)可染色的( 簡(jiǎn)稱七。可染色的) 圖g 的色數(shù)是指g 有一個(gè)正常后頂點(diǎn)染色 的數(shù)k 的最小值，用x ( g ) 表示設(shè)h 是g 的一個(gè)點(diǎn)導(dǎo)出子圖，是日的一個(gè) 后染色，如果g 有一個(gè)七染色妒，使得妒在日上的限制恰好是，則說(shuō)妒是在 g 上的一個(gè)延拓，或者說(shuō)可以延拓到g 本文所用術(shù)語(yǔ)和符號(hào)基本上與文獻(xiàn) 1 】中一致本節(jié)中未介紹的其他圖論術(shù) 語(yǔ)將在必要時(shí)予以闡述 1 23 可染色問題的研究概況 圖的染色問題的研究來(lái)源于著名的四色問題，即在平面上任何一張地圖，總 可以用至多四種顏色給每一個(gè)國(guó)家染色，使得任何兩個(gè)相鄰國(guó)家( 公共邊界上至 少有一段連續(xù)曲線) 的顏色是不同的關(guān)于平面圖的染色問題是圖論界的熱點(diǎn)也 是難點(diǎn) 許多學(xué)者對(duì)平面圖3 可染的問題做了一系列的探討與研究1 9 5 8 年， g r s t z s c h 在文獻(xiàn)【2 中證明了每一個(gè)不含三角形的平面圖是3 ：口- j - 染色的1 9 6 9 年， h a v e l 3 】提出問題：是否存在整數(shù)d ，使得3 一圈之間的距離至少為d 的平面 圖是3 可染的? 并且h a v e l 本人 4 1 證明了若d 存在，則d 2 后來(lái)，a k s i n o v 和m e l n i k o v 5 】將該結(jié)果改進(jìn)到d 4 ，并猜想d = 5 1 9 7 6 年，s t e i n b e r g 提 出了以下猜想： 2 1 緒論 猜想1 1 6 1 每一個(gè)不含4 圈和5 一圈的平面圖是3 可染色的 這個(gè)猜想可以更一般地推廣為： 問題i 1 對(duì)于i i ，i 5 ，使得不含4 ，t 圈的平面圖是3 可染色的，這樣的，是 怎樣一個(gè)正整數(shù)集合? e r d 6 s 在文獻(xiàn) 7 中建議去研究下述問題：是否存在一個(gè)常數(shù)k ，使得不含 4 ，5 ，尼一圈的平面圖是3 可染色的許多學(xué)者圍繞著此猜想做了大量的研 究1 9 9 1 年，a b b o t t 和z h o u 在文獻(xiàn) 8 】中得到了一個(gè)較小的上界k = 1 1 b o r o d i n 9 1 ， s a n d e r s 和z h a o 1 0 1 分別將k 從1 1 降到了9 ，即假若平面圖g 不含4 - 9 圈，那么圖 g 是3 一可染色的在2 0 0 5 年，b o r o d i n 等人在文獻(xiàn) 11 中3 z 再一次把k 從9 降到了 7 從目前已知的研究現(xiàn)狀來(lái)看，研究平面圖的3 可染色的充分條件可以考慮： 問題1 2 是否不含4 ，i ，j ，七一圈( 5 i 歹9 ) 的平面圖都是3 一可染的? 對(duì)于問題1 2 ，不含四類長(zhǎng)度的圈的平面圖的3 染色，已有下面這些研究結(jié) 定理1 1 如果平面圖g 不含以下四類長(zhǎng)度的圈，那么g 是3 可染色的 ( 1 ) 不含4 ，5 ，6 ，7 圈【1 1 1 ； ( 2 ) 不含4 ，5 ，6 ，8 圈【1 2 】； ( 3 ) 不含4 ，5 ，6 ，9 圈【1 3 】； ( 4 ) 不含4 ，5 ，7 ，8 圈； ( 5 ) 不含4 ，5 ，7 ，9 圈【1 5 j ； ( 6 ) 不含4 ，5 ，8 ，9 圈【1 6 】； ( 7 ) 不含4 ，6 ，7 ，8 圈【1 7 1 ； ( 8 ) 不含4 ，6 ，7 ，9 圈； ( 9 ) 不含4 ，6 ，8 ，9 圈【1 9 1 ； 1 1 緒論 ( 1 0 ) 不含4 ，7 ，8 ，9 圈【2 0 1 顯然離解決問題1 1 還有一定距離，可以先研究如下問題： 問題1 3 怎樣的整數(shù)對(duì)( t ，歹) ，其中5 i 歹，能保證不含4 ，i 和歹一圈的平面圖是 3 可染的? 對(duì)于問題1 3 ，許寶剛，王維凡，b o r o d i n 等人己分別得到如下結(jié)果： 定理1 2 如果平面圖g 不含以下三類長(zhǎng)度的圈，那么g 是3 可染色的 ( 1 ) 不含4 ，5 ，7 圈【1 4 】； ( 2 ) 不含4 ，6 ，8 剛2 2 1 ； ( 3 ) 不含4 ，7 ，9 圈【”1 結(jié)合h a v e l 提出的問題 2 乏s t e i n b e r g 猜想，2 0 0 3 年，b o r o d i n 和r a s p a u d 提出了 著名的b o r d e a u x 猜想： 猜想1 2 2 4 1 不含5 圈，且不含相鄰3 圈的平面圖是3 可染色的 關(guān)于猜想1 2 ，b o r o d i n 和許寶剛等人已分別得到如下結(jié)果： 定理1 3 如果平面圖g 不含5 一圈，且3 圈之間的距離至少為d ，那么g 是3 可染 色的 ( 1 ) d = 4 1 2 4 1 ； ( 2 ) d = 3 1 2 5 1 ； ( 3 ) d = 2 2 6 1 1 3 本文的主要結(jié)果 本文在前人的工作基礎(chǔ)上，圍繞上述猜想和問題，運(yùn)用延拓性引理 和d i s c h a r g e 、粘點(diǎn)收縮面等方法，繼續(xù)研究平面圖的3 可染色問題在第二 4 1 緒論 章，第三章和第四章中，給出了平面圖是3 可染色的若干充分條件，分別證明了下 列三個(gè)結(jié)論： ( 1 ) 7 - _ 圈不相鄰的平面圖是3 可染色的； ( 2 ) 不含5 ，7 。圈且不含相鄰三角形的平面圖是3 可染色的； ( 3 ) 不含6 ，8 圈，且3 圈不與3 ，4 一圈相鄰，4 圈不與5 圈相鄰的平面圖是 3 可染色的 顯然本文結(jié)論( 1 ) 改進(jìn)了b o r o d i i l 等人的不含 圈的平面圖是3 可染色的 這一結(jié)果 會(huì)研究結(jié)論( 2 ) 是由于：在2 0 0 6 年，許寶剛證明了不含5 ，7 圈且不含相鄰三 角形的平面圖是3 ，可染色的但是在2 0 0 9 年b o r o d i n 等人找到了該文證明當(dāng)中的 反例( 許寶剛后來(lái)對(duì)自己的證明作了修正) ，并給出了該結(jié)論新的證明這里，筆者 發(fā)現(xiàn)了該結(jié)論的又一種證明 結(jié)論( 3 ) 進(jìn)一步改進(jìn)了王維凡和陳敏的一個(gè)工作：不含4 ，6 ，8 圈的平面圖是 3 可染色的 5 2 沒有相鄰短圈的平面圖的3 染色 本章從沒有相鄰短圈的角度考慮平面圖的3 染色問題，給出了平面圖是3 可 染色的一個(gè)新的充分條件，即 定理2 17 - 圈不相鄰的平面圖是3 可染色的 為證明定理成立，首先需要建立一個(gè)如下的延拓性引理 2 1 延拓性引理 引理2 1 設(shè)g 是一個(gè)7 - _ 圈不相鄰的連通平面圖，是g 中的一個(gè)后面，k 3 ，4 ，5 ，6 ，7 ，8 ，9 ，則，( 準(zhǔn)確地說(shuō)，g 【y ( 刪) 的任意3 一染色都可以延拓到整個(gè)圖g 證明：假設(shè)引理2 1 不成立，設(shè)g 是引理2 1 的關(guān)于盯( g ) = i y ( g ) i + l e ( g ) i 極 小的一個(gè)反例，即g 中有一個(gè)七面1 0 ，k 3 ，4 ，5 ，6 ，7 ，8 ，9 ) ，它有一個(gè)3 一染色( 更 確切地說(shuō)，g 【y ( 如) 的3 一染色) ：y ( f o ) _ 1 ，2 ，3 ) 不能延拓到整個(gè)圖g 不失一 般性，可設(shè)矗是g 中的無(wú)界面，d = 6 ( f o ) 用始( 口) 或d ( v ) 表示點(diǎn)口在g 中的 度數(shù)則引理2 1 的極小反例g 具有以下性質(zhì) 斷言2 1 若u i n t ( d ) ，則d g ( v ) 3 證明：假設(shè)d g ( v ) 2 由g 的極小性可知，前述的可以延拓到g ，= g 一口顯 然，西又可從g 7 延拓到g ，矛盾 斷言2 2g 是2 一連通的因此，g 中任何面的邊界都是一個(gè)圈特別地，d 是一個(gè) 圈 證明：假設(shè)g 不是2 連通的，則g 有割點(diǎn)設(shè)v 是g 的位于終端塊b 上的一個(gè) 割點(diǎn) 6 2 沒有相鄰短圈的平面圖的3 一染色 d id 2 (4)( c ) 圖2 1 含有割點(diǎn)的三種情況 若( b 一 ) nd = 仍( 如圖2 1 ( a ) 和( b ) ) ，則由g 的極小性知，可以延拓到 g 一( b u ) 再根據(jù)b 是否含有三角形來(lái)考慮b 的染色：若b 不含三角形，則 由g r s t z s c h 定理知b 是3 可染的；若b 含有三角形t ，設(shè)7 是t 的任意一個(gè)3 染 色，則由g 的極小性可知，7 可以分別延拓到e x t ( t ) 和x n t ( t ) ，從而延拓到整 個(gè)b 最后，如有必要，對(duì)b 進(jìn)行色置換，可將和調(diào)整為西在g 上的一個(gè)延 拓，矛盾 若( b 一 ) nd d ，則釘將d 分割成兩條閉子途徑d l 和d 2 ( 如圖2 1 ( c ) ) 由g 的極小性可知，咖可以同時(shí)延拓到i n t ( d 1 ) 和，? 砧( d 2 ) ，從而到g ，矛盾 ， 斷言2 3g 沒有分離七一圈，k 3 ，4 ，5 ，6 ，7 ，8 ，9 ) 證明：假設(shè)c 是一個(gè)分離后一圈，k 3 ，4 ，5 ，6 ，7 ，8 ，9 ) 刪去i n t ( c ) ，由g 的極小 性可知，可以延拓到e z t ( c ) 仍根據(jù)g 的極小性，西在c 上的限制可以延拓到 ，m ( g ) 即可以延拓到g ，矛盾 斷言2 4 ( 1 ) 外圈d 無(wú)弦； ( 2 ) 設(shè)c d ，l c i 3 ，4 ，5 ，6 ，7 ，8 】，則c 無(wú)弦； ( 3 ) 設(shè)c d ，i c i = 9 ，則c 至多有一條三角弦 證明：設(shè)e = x y 是d 的一條弦，則z 秒將g 分成兩個(gè)子圖g 1 ，g 2 ( g lng 2 = z y ) ， 根據(jù)極小性，g l ，g 2 外圈上的3 一染色驢可分別延拓到g 1 ，g 2 上，即西可延拓到 整個(gè)g ，矛盾 設(shè)圈c d ，i c i 3 ，4 ，5 ，6 ，7 ，8 ) 因?yàn)間 中長(zhǎng)度不超過7 的圈不相鄰，所以 c 無(wú)弦 7 2 沒有相鄰短圈的平面圖的3 染色 最后，設(shè)圈c d ，i c i = 9 假如c 有非三角弦或至少有兩條三角弦，則g 有相鄰短圈，矛盾 斷言2 5 設(shè)y i n t ( c ) ，z ，z c ，i c i 3 ，4 ，5 ，6 ，7 ，8 ，9 ) ，若z y ，y z e ( g ) ，貝u z 名e ( c ) 證明：首先注意到，由斷言2 1 知，y 至少有一個(gè)鄰點(diǎn)不同于z 和z ，設(shè)為y 7 假 設(shè)c 被路x y z 分成兩個(gè)圈和，不妨設(shè)i c 7 i i c i 假如z 名隹e ( c ) ，則 i c 7 l 4 顯然，i i + i c i = i c i + 4 若i c i 7 ，則4 i c 7 l l c i i c ls7 ，即g 有兩個(gè)相鄰的7 - _ 圈和儼， 矛盾 設(shè)i c i = 8 若i c 7 i = 4 ，則i 伊i = 8 由斷言2 4 可知，y 7 茌c 于是，要么 y 7 i n t ( c ，) ，要么y 7 i n t ( c ) 這時(shí)g 有一個(gè)分離4 一圈或分離8 一圈，與斷言2 3 矛盾因此5 i i 6 i c i 7 這樣，g 有相鄰的7 - _ 圈，矛盾 設(shè)l c l = 9 顯然，4 | l 6 若j c 7 i = 4 ，則i c i = 9 由斷言2 4 可知， y 7 碧下證y 7 垡假若y 7 c ，即可可7 是的一條弦，根據(jù)斷言2 4 ，y y 7 是c 的一條三角弦，這樣g 含有相鄰的3 一圈和4 一圈( 即c ，) 矛盾于是，要么 y 7 i n t ( c ，) ，要么y 7 i n t ( c ) 這時(shí)g 有分離4 一圈或分離9 一圈，與斷言2 3 矛盾 類似可證i c 7 i 5 因此，l c 7 i = 6 這時(shí)顯然有i c i = 7 推出g 有相鄰的7 - 圈， 矛盾 注記2 1 接下來(lái)，為了得到g 的更多的結(jié)構(gòu)性質(zhì)，即斷言2 6 ，將通過“粘點(diǎn)變 換”把g 變成一個(gè)點(diǎn)數(shù)加邊數(shù)更小的圖g ，使得g 7 仍是一個(gè)7 - _ 圈不相鄰的圖， 且仍是g 7 外圈上的點(diǎn)所導(dǎo)出的子圖的3 染色這樣，根據(jù)g 的極小性，可以 延拓到g 7 然后再表明在g 7 上的延拓可修正為妒在g 上的延拓從而得到證 明斷言2 6 所需的矛盾為此，所做的“粘點(diǎn)變換”必需保證以下幾條成立： ( a ) 不產(chǎn)生環(huán)； ( b ) 不產(chǎn)生重邊； ( c ) 不產(chǎn)生相鄰7 - 圈； 8 2 沒有相鄰短圈的平面圖的3 一染色 ( d ) 不會(huì)將d 上的兩個(gè)點(diǎn)粘起來(lái)( 否則d 就不再是一個(gè)圈) ，這樣，d 仍是g ， 的外圈； ( e ) 不會(huì)使d 上兩個(gè)染相同色的點(diǎn)在g 7 中相鄰( 否則g 7 【y ( d ) 】的染色的 正常性被破壞) 斷言2 6 除了d 以外，g 沒有4 ，5 ，6 ，7 圈 證明：假設(shè)g 有一個(gè)不同于d 的七一圈c ，k 4 ，5 ，6 ，7 ) 根據(jù)斷言2 4 ，c 無(wú)弦 又由斷言2 3 知，c 內(nèi)部沒有點(diǎn)，因此，c 是一個(gè)面圈因?yàn)閐 無(wú)弦，所以c 上至 少有一個(gè)點(diǎn)不在d 上設(shè)c = u o u l u 七一1 u o ，k 4 ，5 ，6 ，7 】- ，這里，若c n d d ， 則讓“o c nd ，札1 c d 在由g 圍成的面上將u 1 和讓七一l 粘起來(lái)得到一個(gè)新 圖g 7 ( 同時(shí)u o u l 和u o 饑七一l 被粘成一條邊) 下面驗(yàn)證上述的( n ) 一( e ) 在g 7 中成立 假設(shè)( a ) 不成立，即g 7 中有環(huán)，也即u l u k 一- 是g 中的一條邊這樣，g 有 3 一圈仳。亂1 u k - 1 讓。與4 ，5 ，5 ，7 圈c 相鄰，矛盾 假設(shè)( b ) 不成立，即粘點(diǎn)u l 和七一l 后產(chǎn)生了重邊e l = 讓釘= e 2 ；其中亂是粘 u 1 和亂i ：一l 后產(chǎn)生的點(diǎn)，u u o ( 且當(dāng)k = 4 時(shí)，口u 2 ) ，則圈c 和圈u l u o u k - 1 v u l 是g 中相鄰的7 一圈，矛盾 為了證明( c ) ，即要證明粘點(diǎn)u l 和u 七一l 后，g 7 中仍不含相鄰的7 一。圈注意 到，當(dāng)k = 5 ，6 ，7 時(shí)，在由c 圍成的面上粘點(diǎn)心l 和u k 一- 后會(huì)分別產(chǎn)生3 面( = 釷l 讓2 讓3 u 4 ( = 讓1 ) ) ，4 一面( 厶= u l u 2 u 3 u 4 u 5 ( = u 1 ) ) 和5 - 面( 厶= 仳1 札2 釷3 釷4 亂5 孔6 ( = 亂1 ) ) 顯然 ，尼和如不會(huì)與7 一一圈相鄰否則，在原圖g 中有相鄰的7 一一圈，矛盾因 此，要證( c ) ，只需證粘點(diǎn)u l 和u k 一1 后不會(huì)產(chǎn)生除了 ，2 和1 ：3 以外的新的3 ， 4 ，5 ，6 ，7 圈假設(shè)粘點(diǎn)亂l 和u 七一l 后產(chǎn)生了新的f 圈c 7 = 讓1 口l v 2 v l l z $ k - 1 ( = 讓1 ) ，3 z 7 ，讓我們來(lái)推出矛盾： 若3 z 5 ，則斷言? 2 0 v j ，0 = 1 ，z 一1 ) 否則，將會(huì)得到一個(gè)5 一圈與 c 相鄰，矛盾因此，= 亂l 口l 耽v i - l u k - i u o 讓l 3 z 5 是一個(gè)與c 相鄰的 7 一圈，矛盾 9 2 沒有相鄰短圈的平面圖的3 。染色 設(shè)f = 6 ( 或2 = 7 ) ，可以斷言u(píng) o 0 = 1 ，z 一1 ) 否則，將會(huì)得到一個(gè) 6 一( 或7 - _ ) 圈與g 相鄰，矛盾這樣，c = u l u l v 2 v l - l u k l 釷o u l 是一個(gè)8 一圈 ( 或9 圈) 令p = ? ) l v 2 耽一l ，p 7 = c ( 讓1 ，u o ，u k - 1 ) 顯然，p 7 上至少有一個(gè)頂 點(diǎn)亂t 不在p 上否則的話，g 會(huì)有相鄰的7 - 圈由斷言2 1 知，咖必有異于u 1 和 u 七一的另外一個(gè)鄰點(diǎn)，設(shè)為u 6 設(shè)z = 6 由斷言2 4 知，嵋吻，( 歹= l ，z 一1 ) 因此，缸；i n t ( c ”) 這樣c 是一個(gè)分離8 圈，它分離了u j 和u i ( p ) ，這與斷言 2 3 矛盾設(shè)k = 7 也可以斷言u(píng) o 吻，( j = 1 ，l 一1 ) 假設(shè)亂6 p ，即u o u o 是圈c 的一條弦根據(jù)斷言2 4 ，u o 讓3 必定是一條三角弦但這使得g 有一個(gè) 3 一圈與圈c 相鄰，矛盾因此，玨：i n t ( c ) 這樣c 是一個(gè)分離9 圈，它分離了 u ：和u t ( p ，) ，這與斷言2 3 矛盾這就完成了( c ) 的證明 顯然，( d ) 成立 ( e ) 不成立當(dāng)且僅當(dāng)u o cnd ，u 豇一1 d 且u 1 有一個(gè)不同于u o 的鄰點(diǎn)在 d 上，設(shè)為讓i 由斷言2 5 知，u 1 u o e ( d ) 這使得g 有一個(gè)3 一圈讓l 嵋u o u l 與 7 一圈c 相鄰，矛盾 斷言2 7 設(shè)g 是一個(gè)不含4 ，5 ，6 ，7 一圈的連通的平面圖，則g 中k 面上的點(diǎn)的任 意3 染色，k ，則任取邊e d ，根據(jù)i d l = 4 ，5 ，6 ，7 ，在e 上分別 插入5 ，4 ，3 ，2 個(gè)二度點(diǎn)，則得到一個(gè)沒有4 ，5 ，6 ，7 圈的連通平面圖g 7 現(xiàn)在，將 延拓到這些新的二度點(diǎn)上之后，得到g 7 的外圈( 它是個(gè)9 圈) 上的一個(gè)3 一染色 再根據(jù)斷言2 7 ，這個(gè)3 一染色可以延拓到整個(gè)g ，由此易得在g 上的一個(gè)延拓， 與假設(shè)矛盾，故引理2 1 得證 2 2 定理2 1 的證明 運(yùn)用引理2 i ，可以得到定理2 1 的證明如下：假設(shè)g 是定理2 1 的關(guān)于頂點(diǎn) 數(shù)極小的一個(gè)反例顯然g 是連通的如果g 不含三角形，則i 由g r s t z s c h 的3 色 定理知g 是3 可染的；如果g 含有三角形t ，顯然t 是3 - 可染的設(shè)西是丁的任 意一個(gè)3 一染色，由引理2 1 可知，咖可以分別延拓到e x t ( t ) 和i n t ( t ) ，從而可延 拓到整個(gè)圖g ，矛盾故定理2 1 得證 推論2 1 不含4 ，5 ，6 ，7 一圈的平面圖是3 可染色的 證明：設(shè)g 是任一個(gè)不含4 ，5 ，6 ，7 一圈的平面圖，則g 中的7 - _ 圈不相鄰，根據(jù)定 理2 1 可知g 是3 一訂染色的 3 不含5 ，7 圈的平面圖的3 。染色 定理3 1 不含5 ，7 圈且不含相鄰三角形的平面圖是3 可染色的 該結(jié)論已經(jīng)由許寶剛和b o r o d i n 分別給出證明，本章將給出該結(jié)論的另一種 證明為證明定理成立，首先需要建立一個(gè)如下的延拓性引理 3 1 延拓性引理 引理3 1 設(shè)g 是一個(gè)不含4 ，5 或7 圈的連通平面圖，若，為g 中的七面，其中 k 【3 ，6 ，8 ，9 ，1 0 ，1 1 ，則g 【y ( 刪的任意3 一染色可延拓至整個(gè)圖g 證明：假設(shè)引理3 1 不正確設(shè)g = ( k e ，f ) 為引理3 1 的一個(gè)關(guān)于仃( g ) ( = i y l + i e l ) 極小的反例則有： ( 1 ) g 沒有4 ，5 或7 一圈； ( 2 ) g 有一個(gè)七一面如，其中k 3 ，6 ，8 ，9 ，1 0 ，1 1 ，它有一個(gè)3 一染色( 更確切地說(shuō)， g 【礦( ) 】的一個(gè)3 一染色) ：y ( ) 一( 1 ，2 ，3 】- 不能延拓至整個(gè)圖g ； ( 3 ) 對(duì)任意的滿足盯( g 7 ) 盯( g ) 的不含4 ，5 或7 圈的連通平面圖g ，引理3 1 成 立 不失一般性，可設(shè)局為g 中的外面，且c o = 6 ( i o ) 為其邊界根據(jù)g 的極小 性，g 有如下結(jié)構(gòu)性質(zhì) 斷言3 1g 是2 連通的因此，g 中任意面的邊界都是一個(gè)圈 證明：假設(shè)g 不是2 連通的，即g 含有割點(diǎn)設(shè) 是g 的位于終端塊g 1 上的一 個(gè)割點(diǎn)，并記g 2 = g 一( g l u ) 顯然g i ( i = 1 ，2 ) 仍為不含4 ，5 和7 - 圈的連通 平面圖，且有仃( g i ) 0 ，顯然矛盾由此，引理3 1 得證 掣y u f $ y u f 為方便起見，用t ( x y ) 表示從z 轉(zhuǎn)到y(tǒng) 的權(quán)定義權(quán)轉(zhuǎn)移規(guī)則如下( 參見 圖3 3 ) ： r 1 轉(zhuǎn)給內(nèi)3 一面，的權(quán) 若t 是一個(gè)3 - 面， 是與t 相關(guān)聯(lián)的點(diǎn)，則7 _ _ t ) = j 1 砣 內(nèi)6 + 一面廠轉(zhuǎn)給與它相關(guān)聯(lián)的點(diǎn)口的權(quán) ( a ) 若 是一個(gè)壞3 - 點(diǎn)或f f2 一點(diǎn)，則丁( ，_ u ) = 吾； 1 7 午，器。阜， 一 3 不含5 ，7 一圈的平面圖的3 一染色 ( b ) 若廿是一個(gè)內(nèi)好3 點(diǎn)，或者是與兩個(gè)3 一面相關(guān)聯(lián)的內(nèi)4 點(diǎn)，或者是恰好 關(guān)聯(lián)一個(gè)不與，相鄰的3 一面的內(nèi)4 一點(diǎn)，則t ( f 一口) = i 1 粥 與內(nèi)6 + 面廠相關(guān)聯(lián)的點(diǎn)u 轉(zhuǎn)給l 廠的權(quán) 若”是一個(gè)內(nèi)5 + 點(diǎn)且它與兩個(gè)與，相鄰的3 面相關(guān)聯(lián)，或者是一個(gè)與，o 相 關(guān)聯(lián)的4 + 一點(diǎn)，則r ( v _ ，) = 吾 r 4 如轉(zhuǎn)出的權(quán) 若u 與o 相關(guān)聯(lián)，則，- ( o _ u ) = ； 下面驗(yàn)證z vuf 的新權(quán) 斷言3 9 對(duì)任意 v ，有c 擴(kuò)( u ) 0 若d ( v ) = 2 ，則根據(jù)斷言3 2 知 島由r 2 ( a ) 和l 知，c 擴(kuò)( 口) = 2 4 + ( 吾+ ；) = 0 設(shè)d ( 刀) = 3 若u 是壞3 - 點(diǎn)，則由r 1 和r 2 ( a ) 知，c h * ( v ) - 1 + ；2 一i 1 = o ； 若u 是好點(diǎn)，則由r 2 ( b ) 知，c h + ( 口) - 1 + 3 = o ；若u 在g 上，則由r 4 和 r 1 知，c h * ( v ) - 1 + 虧4 一否1 = 0 設(shè)d ( ”) = 4 若t ，不是內(nèi)點(diǎn)，則由r 4 ，r 3 和r 1 知，c h ( ) 2o + 一吾1x 3 0 若釘不與任何3 面關(guān)聯(lián)，則根據(jù)權(quán)轉(zhuǎn)移規(guī)則，u 既不轉(zhuǎn)出也不轉(zhuǎn)入，即c 擴(kuò)( 鈔) = c h ( v ) = o ；若口恰好關(guān)聯(lián)一個(gè)3 一面，則由r 1 和r 2 ( b ) 知，c h ( 口) 0 一+ = o ； 若口關(guān)聯(lián)兩個(gè)3 - 面，則由r 1 和r 2 ( b ) 知，c h + ( u ) 0 一i 1 2 + j 1 2 = 0 考慮d ( v ) 5 若口不是內(nèi)點(diǎn)，則由r l ，r 3 和r 4 知，c 艫 ) d ( v ) 一4 一 ；( d ( 口) 一1 ) + 否4 0 假設(shè) 是內(nèi)點(diǎn)因?yàn)間 無(wú)相鄰的3 一面，所以由r 1 和r 3 知，口 轉(zhuǎn)給與它相關(guān)聯(lián)的面至多虬掣j 因此，c h ( 口) d ( 口) 一4 ，一；l 掣j 0 斷言3 1 0c h 4 ( f o ) 0 ；, 一, - o - i od ( f o ) 1 1 由r 4 知，c h + ( ) d ( f o ) + 4 一d ( f o ) i 4 = 掣 0 斷言3 1 l 對(duì)任意的，f 矗) ，有如( 廠) 0 1 r 3 不含5 ，7 圈的平面圖的3 一染色 若d ( f ) = 3 ，則根據(jù)r l ，c 礦( 廠) 一1 - f 蠆1x3 = 0 因?yàn)間 沒有4 ，5 或7 圈，所以g 沒有4 ，5 或7 面 設(shè)，是一個(gè)6 一面由于g 沒有7 一圈，所以，不與任何3 一面相鄰，因此，不 與任何壞點(diǎn)相關(guān)聯(lián)若，關(guān)聯(lián)一個(gè)2 一點(diǎn)，則，與矗至少有三個(gè)公共點(diǎn)由斷言 3 5 知，與如恰好有三個(gè)公共點(diǎn)，一個(gè)是2 點(diǎn)，其它兩個(gè)是3 + 點(diǎn)根據(jù)權(quán)轉(zhuǎn)移規(guī) 則，不轉(zhuǎn)給這兩個(gè)3 + 一點(diǎn)任何權(quán)因此，根據(jù)r 2 有c h + ( ，) = 2 一；一蠆1 3 0 這樣，可以假定，不與任何2 一點(diǎn)關(guān)聯(lián)這時(shí)，轉(zhuǎn)給與它相關(guān)聯(lián)的點(diǎn)至多互1 因此， c h * ( f ) 6 4 一 6 = 0 設(shè)，是一個(gè)8 + 一面若，至少關(guān)聯(lián)一個(gè)2 - 點(diǎn)，則，至少關(guān)聯(lián)兩個(gè)在扁上 的3 + 一點(diǎn)，而根據(jù)規(guī)則，不轉(zhuǎn)任何權(quán)給這兩個(gè)3 + - 點(diǎn)因此根據(jù)r 2 ( a ) ，c h + ( ，) d ( f ) 一4 一( d ( ，) 一2 ) ；她3 0 接下來(lái)，假定f 不與任何2 點(diǎn)關(guān)聯(lián) 設(shè)d ( f ) 1 2 由r 2 ( a ) 知，轉(zhuǎn)給與它相關(guān)聯(lián)的點(diǎn)至多；因此，c 艫( ，) d ( f ) 一4 一i d ( ，) 0 設(shè)d ( f ) = 1 1 根據(jù)奇偶對(duì)等性，至多與十個(gè)壞3 點(diǎn)相關(guān)聯(lián)因此，如( ，) 1 1 4 一；x1 0 一i 1 = 0 設(shè)d ( 1 ) = 1 0 因?yàn)間 沒有四串，所以任何五個(gè)壞點(diǎn)不會(huì)連續(xù)出現(xiàn)在，的邊 界上這使得廠至多關(guān)聯(lián)八個(gè)壞3 一點(diǎn)因此，c h 4 ( 廠) 6 一x8 一吾1 x2 = 0 設(shè)d ( f ) = 9 由g 沒有四串知，至多關(guān)聯(lián)七個(gè)壞