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

上官敏樂

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

引言

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

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

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

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

本文討論的是完備染色問題。文中未加定義的術語和記號請參閱文獻[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 的完備色數χ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 的列表完備色數，或稱完備選擇數chT(G)是使得G 是k 完備可選擇的最小的非負整數k.

一、引理

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

引理2 2－點只能與11－點相鄰。

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

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

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

引理4 若G 內不含有一個5-面關聯2 個3-點,且這兩個3-點相鄰。

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

二、定理1 的證明

權轉移規則：

R1:11－點轉移1 給相鄰的2－點。

以下考察頂點的新權：

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

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

其次考察面的新權：