Δ(G)=8且不含5-圈的平面圖的完備染色

張巖

（浙江樹人大學 基礎部，浙江 杭州 310015）

一、引言

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

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

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

圖論是門應用十分廣泛且內容非常豐富的數學分支，它在生產管理，軍事，交通運輸，計算機網絡等許多領域都有重要的應用。在圖論的歷史中，還有一個最著名的問題－－四色猜想。這個猜想說，在一個平面或球面上的任何地圖能夠只用四種顏色來著色，使得沒有兩個相鄰的國家有相同的顏色。每個國家必須由一個單連通域構成，而兩個國家相鄰是指它們有一段公共的邊界，而不僅僅只有一個公共點。這一問題最早于1852 年由Francis Guthrie 提出，最早的文字記載則現于德摩根于同一年寫給哈密頓的信上。包括凱萊、肯普等在內的許多人都曾給出過錯誤的證明。泰特(Tait)、希伍德(Heawood)、拉姆齊和哈德維格(Hadwiger)對此問題的研究與推廣引發了對嵌入具有不同虧格的曲面的圖的著色問題的研究。一百多年后，四色問題仍未解決。1969 年，Heinrich Heesch 發表了一個用計算機解決此問題的方法。1976 年，阿佩爾(Appel)和哈肯(Haken)借助計算機給出了一個證明，此方法按某些性質將所有地圖分為1936 類并利用計算機，運行了1200個小時，驗正了它們可以用四種顏色染色。四色定理是第一個主要由電腦證明的理論，這一證明并不被所有的數學家接受，因為采用的方法不能由人工直接驗證。最終，人們必須對電腦編譯的正確性以及運行這一程序的硬件設備充分信任。主要是因為此證明缺乏數學應有的規范，以至于有人這樣評論“一個好的數學證明應當像一首詩——而這純粹是一本電話簿！”染色問題是圖論的重要內容，也是圖論的起源之一，具有重要的理論意義和實際意義。幾百年來，它深深汲引著數學家們的注意力，圖的染色問題又有很多種分類，如頂點染色，邊染色，全染色，點面染色，邊面染色，完備染色等等。關于平面圖的染色問題一直是圖論界的研究熱點。

本文討論的是完備染色問題。平面圖G 的一個完備染色是指一個映射 φ:V(G) ∪E(G) ∪F(G)→{1,2....,k},滿足對于任意不同的相鄰或相關聯的元素x,y∈V(G)∪E(G) ∪F(G),都有φ(x)≠φ(y)。G的完備色數是指G 有一個完備k-染色的數k 的最小值。

文中未加定義的術語和記號請參閱文獻[1].用V,E,Fδ和Δ 分別表示平面圖G 的頂點集,邊集,面集,最小度和最大度.設v 是圖G 的一個頂點,于v 相關聯的邊的條數叫做v 的度數,記作d（v）,若d（v）=k (d（v）≥k),則稱v 為一個k－點（≥k－點）。在平面圖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 個顏色進行染色,使得相鄰或相關聯的元素都接受不同的顏色,則稱G 是k 完備可染的,G 的完備色數

關于平面圖的完備染色是Ringel（1965）提出的，Kronk 和Mitchem[2]猜想:對任何簡單圖G,(G)+4.Borodin[3]已在1993 年證明了對于任意的平面圖G：若△(G) ≥12，(G)+2。并且后來他提出了一個問題，對于△(G) ≤11 的平面圖G，能否找到完備色數的一個緊的上界？對于△(G) ≥7 的平面圖G，Borodin 證明了(G)+4.對 于△(G) ≥6 的 平 面 圖G，Dong 證 明 了(G)+5.本文證明:定理1:若△(G)=8 的平面圖G 且不含有4 -圈,則χvef(G)≤△(G)+4 ＝12.

二、引理

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

引理2 設uv 是G 的一條邊，若d（u）＝2，則d（u）＋d（v）≥ 10。即2－點只能與8－點相鄰。

證明：假設d（v）≤6，且設u 相鄰的另一個點為w，由引理1 可得G－{u}+{vw}是簡單圖,且是10－完備可染的，現在把vw 的色染給uw，則依次可染上uv，u。

引理3 任意點u 關聯一個3-面，則d（u）≥4

證明：假設存在點u,關聯一個3-面f，且d（u）=2，設與邊uv 關聯的另一個面為f1，設與點u 相鄰的另兩個點為v，w,則G－{u}是10－完備可染的，現在對G 進行染色，把面{f∪f1}的顏色染給f1，則可依次可染上邊uv，vw,面f，點u。假設存在點u,關聯一個3-面f，且d（u）=3，設與點u 相鄰的另兩個點為v，w,則G－{uv}是10－完備可染的，設與邊uv 關聯的另一個面為f1，把面{f∪f1}的顏色染給f1，刪去u 的色，現在對G 進行染色，則可依次可染上邊uv，面f，點u。

引理4 若G 內有一個4-面關聯2 個≤3-點,則G 是12－完備可染的.

證明：假設存在一個4-面f，關聯2 個≤3-點u,v,，則G－{u,v}是12－完備可染的，現在對G 進行染色，可依次可染上面f,與u,v 相關聯的四條邊,以及點u,v.

三、定理1 的證明

權轉移規則：R1:v－點轉移 1 給相關聯的3-面。其中4 ≤ d（v）≤5。

R2: 8－點轉移1 給相鄰的2－點，1給相關聯的3－面。

R3: ≥4-點轉移1 給相關聯的4－面。

以下考察頂點的新權：

2－點v：由引理2 及R2，w′(v) ＝－2＋2 ＝0；3－點v：w′(v)＝w(v)＝0

v－點：4 ≤ d（v）≤6，由R1，R3，w′(v)〉0；

其次考察面的新權：

3-面f：由引理3，f 不關聯2-點，3-點。即f 關聯三個≥4-點則由R1，R2，w′(v)=－3+3×1 ＝0.≥6 -面f：w′ (f)≥0。

4-面f:由R3，w′(v)=－1+1 ＝0.≥6 -面f：w′(f)≥0