張巖

【摘要】用xvef（G）分別表示圖G的完備色數(shù)。本文證明：若△（G）=6的平面圖G且不含有4-圈，5-圈，則xvef（G）≤△（G）+4。

【關(guān)鍵詞】△（G）=6 平面圖 完備色數(shù)

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

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

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

本文討論的是完備染色問題。平面圖G的一個完備染色是指一個映射ψ：V（G）∪E（G）∪F（G）→{1，2，…，k），滿足對于任意不同的相鄰或相關(guān)聯(lián)的元素x，y∈V（G）∪E（G）∪F（G）都有ψ（x）≠ψ（y）。G的完備色數(shù)是指G有一個完備k-染色的數(shù)k的最小值。

文中未加定義的術(shù)語和記號請參閱文獻[1].用V，E，F(xiàn)δ和△分別表示平面圖G的頂點集，邊集，面集，最小度和最大度.設(shè)v是圖G的一個頂點，于v相關(guān)聯(lián)的邊的條數(shù)叫做v的度數(shù)，記作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個顏色進行染色，使得相鄰或相關(guān)聯(lián)的元素都接受不同的顏色，則稱G是k完備可染的，G的完備色數(shù)xvef（G）=min{kG是k-完備可染的}.

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

一、引理

設(shè)G是滿足定理1但不是10-完備可染的且6（G）=|V|+|E|盡可能小的這樣一個平面圖，則不難證明：

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

引理2 設(shè)uv是G的一條邊，若d（u）=2，則d（u）+d（v）≥8。即2-點只能與6-點相鄰。

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

引理3 任意點u關(guān)聯(lián)一個3面，則d（u）≥4

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

引理4 若G內(nèi)有一個5-面關(guān)聯(lián)2個2-點，則G是11-完備可染的.

證明：假設(shè)存在一個5-面f，關(guān)聯(lián)2個2-點u，v，則G-{u，v}是11-完備可染的，現(xiàn)在對G進行染色，可依次可染上面f，與u，v相關(guān)聯(lián)的四條邊，以及點u，v.

二、定理1的證明

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

3-面f：由引理3，f不關(guān)聯(lián)2-點，3-點。即f關(guān)聯(lián)三個≥4-點則由R1，R2，w'（v）=-3+3×1=0.≥6-面f：w'（f）≥0。

參考文獻：

[1]J. A. Bondy， O. S. R. Murty. Graph Theory with Applica-tions[M]. New York：Macmillan， 1976.

[2]H. Kronk and J. Mitchem， A seven-color theorem on thesphere[J]. Discrete Math， 1973， （6）.＼

[3]O.V. Borodin， The structure of edge neighborhoods in pla-nat graph and the Simultaneous coloring of the vertices， edgesand faces[J]. Metem. Zametki， 1993， （53）.

[4]Wang Weifan， Upper bounds of entire chromatic number ofplane graphs[J]. Europ. J. Combinatorics， 1999， （20）.

[5]Daniel P. Sanders and Yue Zhao， On the entire coloringconjecture[J]. Canad. Math. Bull. Vol， 2000， （43）.

[6]O.V. Borodin， Structure theorem on plane graphs with ap-plication to the entire coloring number [J]. Journal of graphtheory vol，1996， （23）.

[7]吳建良，平面圖的完備染色[J].山東礦業(yè)學院學報，1994，（13）.

[8]王維凡，關(guān)于完備色數(shù)[J].遼寧大學學報，1995，（22）.