Δ(G)=11且不含有三角形,4-圈的平面圖的完備染色

上官敏樂

（浙江樹人大學(xué) 基礎(chǔ)部，浙江 杭州 310015）

引言

圖論起源于一個非常經(jīng)典的問題——柯尼斯堡（Konigsberg）問題。

1738 年，瑞典數(shù)學(xué)家歐拉(Leornhard Euler)解決了柯尼斯堡問題。由此圖論誕生。歐拉也成為圖論的創(chuàng)始人。

1859 年，英國數(shù)學(xué)家漢密爾頓發(fā)明了一種游戲：用一個規(guī)則的實(shí)心十二面體，它的20 個頂點(diǎn)標(biāo)出世界著名的20 個城市，要求游戲者找一條沿著各邊通過每個頂點(diǎn)剛好一次的閉回路，即“繞行世界”。用圖論的語言來說，游戲的目的是在十二面體的圖中找出一個生成圈。這個生成圈后來被稱為漢密爾頓回路。這個問題后來就叫做漢密爾頓問題。由于運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和編碼理論中的很多問題都可以化為漢密爾頓問題，從而引起廣泛的注意和研究。

在圖論的歷史中，還有一個最著名的問題－－四色猜想。這個猜想說，在一個平面或球面上的任何地圖能夠只用四種顏色來著色，使得沒有兩個相鄰的國家有相同的顏色。每個國家必須由一個單連通域構(gòu)成，而兩個國家相鄰是指它們有一段公共的邊界，而不僅僅只有一個公共點(diǎn)。這一問題最早于1852 年由Francis Guthrie 提出，最早的文字記載則現(xiàn)于德摩根于同一年寫給哈密頓的信上。包括凱萊、肯普等在內(nèi)的許多人都曾給出過錯誤的證明。泰特(Tait)、希伍德(Heawood)、拉姆齊和哈德維格(Hadwiger)對此問題的研究與推廣引發(fā)了對嵌入具有不同虧格的曲面的圖的著色問題的研究。一百多年后，四色問題仍未解決。1969 年，Heinrich Heesch 發(fā)表了一個用計(jì)算機(jī)解決此問題的方法。1976 年，阿佩爾(Appel)和哈肯(Haken)借助計(jì)算機(jī)給出了一個證明，此方法按某些性質(zhì)將所有地圖分為1936類并利用計(jì)算機(jī)，運(yùn)行了1200 個小時，驗(yàn)正了它們可以用四種顏色染色。四色定理是第一個主要由電腦證明的理論，這一證明并不被所有的數(shù)學(xué)家接受，因?yàn)椴捎玫姆椒ú荒苡扇斯ぶ苯域?yàn)證。最終，人們必須對電腦編譯的正確性以及運(yùn)行這一程序的硬件設(shè)備充分信任。

本文討論的是完備染色問題。文中未加定義的術(shù)語和記號請參閱文獻(xiàn)[1].用V,E,Fδ和Δ分別表示平面圖G 的頂點(diǎn)集,邊集,面集,最小度和最大度.設(shè)v 是圖G 的一個頂點(diǎn),于v 相關(guān)聯(lián)的邊的條數(shù)叫做v 的度數(shù),記作d（v）,若d（v）=k(d（v）≥k),則稱v 為一個k－點(diǎn)（≥k－點(diǎn)）。在平面圖G 中，面f ∈F(G),用b（f）表示圍繞面f 的閉途徑。把閉途徑b（f）的長度稱為面f 的度，記為d（f），若d（f）＝k（d（f）≥k），則稱f為一個k-面（≥k-面）。

若V ∪E ∪F 中的元素能用k 個顏色進(jìn)行染色,使得相鄰或相關(guān)聯(lián)的元素都接受不同的顏色,則稱G 是k 完備可染的,G 的完備色數(shù)χvef(G)=min{kG 是k-完備可染的}.Kronk 和Mitchem[2]猜想:對任何簡單圖G,χvef(G)≤△(G)+4.Borodin[3]已證明：若△(G) ≥12，χvef(G)≤△(G)+2。本文證明:

定理1:若△(G)=11 的平面圖G 且不含有三角形,4-圈,則χvef(G)≤△(G)+2＝13.

圖G 的一個完備色列表是一個顏色集合簇L，對G 的每個元素x∈V ∪E ∪F 都配一個顏色集合L（x）.若G 一個正常完備染色φ(x)，使得每個元素，則稱G 是L 全可染的。若對每一個滿足能，x∈V ∪E ∪F 的完備色列表L,G 都是L 完備可染的，則稱G 是k 完備可選擇的，G 的列表完備色數(shù)，或稱完備選擇數(shù)chT(G)是使得G 是k 完備可選擇的最小的非負(fù)整數(shù)k.

一、引理

引理1 G 是2－連通的，從而δ≥2且G 的每個面的邊界都是圈。

引理2 2－點(diǎn)只能與11－點(diǎn)相鄰。

證明：假設(shè)2－點(diǎn)與點(diǎn)v 相鄰，d（v）<11，且設(shè)2－點(diǎn)u 相鄰的另一個點(diǎn)為w，由引理1 可得G－{u}+{vw}是簡單圖,且是13－完備可染的，現(xiàn)在把vw 的色染給uw，考察邊uv，至多關(guān)聯(lián)11 個元素，故可染邊uv，再考察點(diǎn)u，關(guān)聯(lián)6 個元素，故可染，最后考察面uvw，至多關(guān)聯(lián)8 個元素，故可染，即G 是13－完備可染的，所以矛盾，即2－點(diǎn)只能與11－點(diǎn)相鄰。

引理3 設(shè)uv 是G 的一條邊，d（u）=3,則d（v）>9。

證明：設(shè)u相鄰的另一個點(diǎn)為w,由引理1可得G－{uv}+{vw}是簡單圖,且是13－完備可染的，現(xiàn)在先刪去u 的顏色,把vw 的色染給uw，則依次可染上uv，u。

引理4 若G 內(nèi)不含有一個5-面關(guān)聯(lián)2 個3-點(diǎn),且這兩個3-點(diǎn)相鄰。

證明：假設(shè)存在一個5-面f，關(guān)聯(lián)2個3-點(diǎn)u,v,，由引理1可得G－{uv}是簡單圖,且是13－完備可染的。現(xiàn)在對G 進(jìn)行染色，先刪除5-面f，點(diǎn)u，v 的顏色，考察f 至多關(guān)聯(lián)12 個顏色，故可染，再考察點(diǎn)u，點(diǎn)v，邊uv 分別至多關(guān)聯(lián)9 個顏色，故全部可染，則G是13－完備可染的，所以矛盾，即G 內(nèi)不含有一個5-面關(guān)聯(lián)2 個3-點(diǎn),且這兩個3-點(diǎn)相鄰。

二、定理1 的證明

權(quán)轉(zhuǎn)移規(guī)則：

R1:11－點(diǎn)轉(zhuǎn)移1 給相鄰的2－點(diǎn)。

以下考察頂點(diǎn)的新權(quán)：

2－點(diǎn)v：由引理2 及R1，w′(v)＝－2＋2＝0；3－點(diǎn)v：w′(v)＝w(v)＝0

v－點(diǎn)：4 ≤d（v）≤5，w(v)>0；

其次考察面的新權(quán)：