張巖

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

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

引言

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

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

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

圖論是門應(yīng)用十分廣泛且內(nèi)容非常豐富的數(shù)學(xué)分支，它在生產(chǎn)管理，軍事，交通運(yùn)輸，計(jì)算機(jī)網(wǎng)絡(luò)等許多領(lǐng)域都有重要的應(yīng)用。在圖論的歷史中，還有一個(gè)最著名的問(wèn)題--四色猜想。這個(gè)猜想說(shuō)，在一個(gè)平面或球面上的任何地圖能夠只用四種顏色來(lái)著色，使得沒(méi)有兩個(gè)相鄰的國(guó)家有相同的顏色。每個(gè)國(guó)家必須由一個(gè)單連通域構(gòu)成，而兩個(gè)國(guó)家相鄰是指它們有一段公共的邊界，而不僅僅只有一個(gè)公共點(diǎn)。這一問(wèn)題最早于1852年由Francis Guthrie提出，最早的文字記載則現(xiàn)于德摩根于同一年寫給哈密頓的信上。包括凱萊、肯普等在內(nèi)的許多人都曾給出過(guò)錯(cuò)誤的證明。泰特（Tait）、希伍德（Heawood）、拉姆齊和哈德維格（Hadwiger）對(duì)此問(wèn)題的研究與推廣引發(fā)了對(duì)嵌入具有不同虧格的曲面的圖的著色問(wèn)題的研究。一百多年后，四色問(wèn)題仍未解決。1969年，Heinrich Heesch發(fā)表了一個(gè)用計(jì)算機(jī)解決此問(wèn)題的方法。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)像一首詩(shī)——而這純粹是一本電話簿！”染色問(wèn)題是圖論的重要內(nèi)容，也是圖論的起源之一，具有重要的理論意義和實(shí)際意義。幾百年來(lái)，它深深汲引著數(shù)學(xué)家們的注意力，圖的染色問(wèn)題又有很多種分類，如頂點(diǎn)染色，邊染色，全染色，點(diǎn)面染色，邊面染色，完備染色等等。關(guān)于平面圖的染色問(wèn)題一直是圖論界的研究熱點(diǎn)。

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

文中未加定義的術(shù)語(yǔ)和記號(hào)請(qǐng)參閱文獻(xiàn)，用V，E，F(xiàn)δ和△分別表示平面圖G的頂點(diǎn)集，邊集，面集，最小度和最大度.設(shè)v是圖G的一個(gè)頂點(diǎn)，于v相關(guān)聯(lián)的邊的條數(shù)叫做v的度數(shù)，記作d（v），若d（v）=k （d（v）≥k），則稱v為一個(gè)k-點(diǎn)（≥k-點(diǎn)）。在平面圖G中，面fF（G），用b（f）表示圍繞面f的閉途徑。把閉途徑b（f）的長(zhǎng)度稱為面f的度，記為d（f），若d（f）=k（d（f）≥k），則稱f為一個(gè)k-面（≥k-面）。

若V∪E∪F中的元素能用k個(gè)顏色進(jìn)行染色， 使得相鄰或相關(guān)聯(lián)的元素都接受不同的顏色，則稱G是k完備可染的，G的完備色數(shù)xvef（G）=min{kG是k-完備可染的}。

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

二、引理

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

引理1;G至少有兩個(gè)二度點(diǎn)。

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

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

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

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

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

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

引理5 一個(gè)4-點(diǎn)至多關(guān)聯(lián)2個(gè)>4-面.

三、定理1的證明

設(shè)G是定理1的一個(gè)使得δ（G）=|V|+|E|最小的反例，由歐拉公式（2d（v）-6）+（d（f）-6）=-12，現(xiàn)在給G的點(diǎn)v分配權(quán)w（v）=2d（v）-6，給G的面f分配權(quán)w（f）=d（f）-6，所以w`（x）=-12<0，然后根據(jù)下面的權(quán)轉(zhuǎn)移規(guī)則，重新分配點(diǎn)和面的權(quán)，得w`（x）≥0，便得出矛盾，即定理得證。

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

R1：8-點(diǎn)轉(zhuǎn)移1給相鄰的2-點(diǎn)。

R2：8-點(diǎn)轉(zhuǎn)移1給相關(guān)聯(lián)的4-面。

R3：8-點(diǎn)轉(zhuǎn)移給相關(guān)聯(lián)的5-面。

R4：>3-點(diǎn)轉(zhuǎn)移1給相關(guān)聯(lián)的4-面。

以下考察頂點(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）≤7，由引理5和R4，w`（v）>0;

8-點(diǎn)：R1，R2，w`（v）=10-8>0

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

4-面f：由引理5， f不關(guān)聯(lián)2-點(diǎn)，3-點(diǎn)。即f關(guān)聯(lián)兩個(gè)個(gè)≥4-點(diǎn) 則由R2，R4，w`（v）=-3+=0.-面f：w`（f）≥0。

5-面f：R3，w`（v）=-1+1=0.-面f：w`（f）≥0。

參考文獻(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）.