[Δ]（G）=8且不含4-圈的平面圖的完備染色

張巖

◆摘 ?要：用xvef（G）分別表示圖G的完備色數(shù)。本文證明：若[Δ]（G）=8的平面圖G且不含有4-圈，則xvef（G）≤[Δ]（G）+4。

◆關(guān)鍵詞：[Δ]（G）=8;平面圖;完備色數(shù)

1引言

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

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

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

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

參考文獻(xiàn)

[1]J.A.Bondy，U.S.R.Murty.Graph Theory with Applications[M].New York：Macmillan，1976.

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

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

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

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

[6]O.V.Borodin.Structure theorem on plane graphs with application to the entire coloring number [J].Journal of graph theory vol，1996（23）.

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

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