平面圖3可著色的一個(gè)充分條件

趙春紅

（沙洲職業(yè)工學(xué)院建筑工程系，江蘇張家港215600）

平面圖3可著色的一個(gè)充分條件

趙春紅

（沙洲職業(yè)工學(xué)院建筑工程系，江蘇張家港215600）

為研究平面圖的3著色問題，運(yùn)用文獻(xiàn)[1]中權(quán)轉(zhuǎn)移的方法證明了一類平面圖3可著色的一個(gè)充分條件，即：不含5-圈，且每個(gè)4-圈，6-圈或7-圈不與長(zhǎng)度小于8的圈有公共邊的平面圖是3-可著色的。

平面圖；圈；著色

圖的點(diǎn)著色問題[2]一直是圖論學(xué)者研究的熱點(diǎn)，從四色問題的提出，到著名五色定理，最后學(xué)者們把點(diǎn)著色的研究重點(diǎn)放在平面圖的3著色上，出現(xiàn)很多猜想，得到很多結(jié)論。針對(duì)Erd?s提出的關(guān)于平面圖3著色的猜想（是否存在整數(shù)k，使得每個(gè)不含4至k圈的平面圖是3-可著色的），無數(shù)圖論學(xué)者都致力于把這個(gè)未知數(shù)k降低到最小：1991年，Abbott和Zhou把k降低到了11，2005年Borodin和Raspaud等人把k降低到了7，目前更小的k值還未得到證明。筆者通過增加一些附加條件，在文獻(xiàn)[3]中證明了兩個(gè)結(jié)論：（1）每一個(gè)不含4-6圈，也不含距離小于2的三角形對(duì)，且每個(gè)7-圈最多與一個(gè)三面相鄰的平面圖是3-可著色的；（2）每一個(gè)不含4-圈和5-圈，且每個(gè)6-圈或7-圈不與長(zhǎng)度小于8的圈有公共邊的平面圖是3-可著色的。在該文中，所研究的圖為有限簡(jiǎn)單圖，除特別定義外，所使用的術(shù)語、概念、符號(hào)都與文獻(xiàn)[2]中一致。

設(shè)Γ是不含5-圈，且每個(gè)4-圈，6-圈或7-圈不與長(zhǎng)度小于8的圈有公共邊的平面圖集合。筆者將繼續(xù)運(yùn)用權(quán)轉(zhuǎn)移的方法，在文中證明：

定理1?G∈Γ，χ（G）≤3，其中χ（G）為G的色數(shù)。

要證明此結(jié)論，需要先討論一類極小平面圖的結(jié)構(gòu)及其存在性。

1 一類極小平面圖的結(jié)構(gòu)討論

假設(shè)存在G∈Γ，是一個(gè)邊數(shù)和點(diǎn)數(shù)之和|E（G）|+|V（G）|=δ（G）最少的且存在G中的某一個(gè)4-圈或長(zhǎng)為6至11的圈f0的邊界D的導(dǎo)出子圖的3-著色φ不可擴(kuò)充到整個(gè)圖G的極小平面圖。筆者在文獻(xiàn)[4]中已經(jīng)證得圖G的以下8個(gè)結(jié)論：

（1）G中不含有長(zhǎng)度小于等于11的分離圈S。

（2）G中圈長(zhǎng)為4、6至8的圈不含有弦，圈長(zhǎng)為9至11的圈不含有非三角形的弦。

（3）D是一個(gè)簡(jiǎn)單圈，無弦。

（4）G是2連通的。

（5）G的每一個(gè)2度點(diǎn)都屬于D，且沒有一個(gè)2度點(diǎn)與一個(gè)3面相關(guān)。

（6）G中的6-圈或7-圈都不與三角形有公共邊。

（7）除f0外，任何兩個(gè)面都不可能正好擁有兩條相鄰的公共邊。

（8）G中無四元組。

根據(jù)已有結(jié)論，D在G中界定一個(gè)面，不妨設(shè)f0為圈D界定的面且為G的外部面，若G含有內(nèi)部4-圈，則該4-圈一定是4-面。由文獻(xiàn)[5]，可證明以下結(jié)論。

引理1G不含有內(nèi)部4-面。

證明假設(shè)G中含有內(nèi)部4-面f，其邊界為T=uvwxu，則f不可能與長(zhǎng)度小于8的圈有公共邊。f也不可能與長(zhǎng)度為9的圈有兩條相鄰的公共邊。否則，設(shè)有兩條相鄰的公共邊uv，vw，則v點(diǎn)的度不可能是2，否則G是3-可著色的。因此，在該9-圈內(nèi)部存在一點(diǎn)v′是v的鄰點(diǎn)，而該9-圈就分離了v′和x，與8個(gè)結(jié)論中的結(jié)論（1）矛盾。

設(shè)Guw表示粘合u和w得到的平面圖，Gvx表示粘合v和x得到的平面圖，則：

（1）Guw不含有5-圈，否則在G中會(huì)產(chǎn)生4-圈與7-圈有公共邊的情形，與G的選取矛盾。

（2）若粘合u和w得到的平面圖Guw不會(huì)產(chǎn)生新的3-圈、4-圈、6-圈和7-圈，則由G的選取，顯然Guw是3可著色的，從而得到G的3著色，矛盾。

（3）粘合u和w得到的平面圖Guw不會(huì)產(chǎn)生新的3-圈、4-圈，否則在G中會(huì)產(chǎn)生4-圈與6-圈有公共邊的情形，與G的選取矛盾。

以上（1）、（2）、（3）對(duì)于Gvx同樣成立。

（4）從而，不妨設(shè)粘合u和w得到的平面圖Guw會(huì)產(chǎn)生新的6-圈和7-圈，且粘合v和x得到的平面圖Gvx也會(huì)產(chǎn)生新的6-圈和7-圈。

因此，存在一條路p1連接u和w，一條路p2連接v和x，其中p1、p2的長(zhǎng)度為6或7。由于G是平面圖，則p1{u，w}，p2{v，x}有一個(gè)公共點(diǎn)。但V（p1）∩{v，x}=Φ，V（p2）∩{u，w}=Φ。否則，在G中會(huì)出現(xiàn)f與某個(gè)長(zhǎng)度小于8的圈有公共邊的情況，與G的選取矛盾。設(shè)P1=ub1b2b3bl1-1，（l1=5，6），且假設(shè)bi∈{V（pi）}為p1、p2的唯一公共點(diǎn)。設(shè)對(duì)于每一條路p和p上的不同點(diǎn)u、w，用p[u，w]表示p中連接u、w的一部分路。設(shè)pu=p1[u，bi]，pw= p1[bi，w]，pv=p2[v，bi]，px=p2[bi，x]，對(duì)于s∈{u，v，w，x}，設(shè)ls表示路ps的長(zhǎng)度，則由G的選取，有

通過計(jì)算可以發(fā)現(xiàn)，這個(gè)方程組無解。因此，平面圖Guw和Gvx中至少有一個(gè)不會(huì)產(chǎn)生新的6-圈和7-圈。

假設(shè)Guw不會(huì)產(chǎn)生新的6-圈和7-圈。綜合以上討論，Guw?Γ，且為比G的邊少的平面圖，因此，如果粘合u、w得到的平面圖Guw沒有破壞D的著色的話，則可以把D的著色擴(kuò)充到Guw，從而擴(kuò)充到G，矛盾。

現(xiàn)在證明D的著色φ不會(huì)被粘合u和w所破壞。若被破壞，則意味著粘合u和w出現(xiàn)了兩種結(jié)果：（a）粘合了D中著以不同顏色的點(diǎn)；（b）把D中著相同顏色的兩個(gè)點(diǎn)連成邊。總之，這兩種情況都說明了u和w到D的距離之和最多為1。

設(shè)D=d1d2…d|D|，按照順時(shí)針順序遞增排列，設(shè)d|D|是D中離u最近的點(diǎn)，而dj是離w最近的點(diǎn)，因?yàn)閨D|≤11，所以D被dj和d|D|分成兩條路P1，P2，設(shè)P1＝d|D|d1…dj，至多有5條邊，這條路與路djuv3v2v1wd|D|相關(guān)，產(chǎn)生一個(gè)圈長(zhǎng)至多為11的圈C，矛盾。

因此，G中不含有內(nèi)部4-面。

2 極小平面圖G的存在性討論

關(guān)于極小平面圖G的存在性討論如下：

（1）若f0≠4，則G為不含有4-圈和5-圈，且每個(gè)6-圈或7-圈都不與長(zhǎng)度小于8的圈有公共邊的平面圖，由文獻(xiàn)[3]可知，G是3-可著色的，矛盾。

（2）若f0＝4，下面將用權(quán)轉(zhuǎn)移的方法證明極小平面圖G不存在。

不要將教師擺在一個(gè)主導(dǎo)學(xué)生的地位，要把自己放在與學(xué)生平等的位置，和學(xué)生共同學(xué)習(xí)，共同進(jìn)步.課堂上要把盡量多的時(shí)間留給學(xué)生，減少講課的時(shí)間，引導(dǎo)學(xué)生自主學(xué)習(xí)，如：我們?cè)诰蛯W(xué)習(xí)《命題及其關(guān)系》這一部分時(shí)，我們用2課時(shí)進(jìn)行學(xué)習(xí)，其中第一課時(shí)時(shí)我們只抽出15分鐘時(shí)間來講解基礎(chǔ)知識(shí)，其余時(shí)間交給學(xué)生，可以讓學(xué)生來講解一部分知識(shí)或題目，讓學(xué)生提出問題并讓其他學(xué)生來回答，老師進(jìn)行糾正;在第二課時(shí)時(shí)，老師可以對(duì)大部分學(xué)生不能理解的內(nèi)容重點(diǎn)講解，然后讓學(xué)生討論本節(jié)的收獲，整理重難點(diǎn).這種教學(xué)理念也可以幫助學(xué)生轉(zhuǎn)變自己的思維方式，使自己的數(shù)學(xué)思維更加發(fā)散.

對(duì)于?x∈（V（G）∪F（G））{f0}，令w（x）=d（x）-4，對(duì)于f0，令w（x）=d（x）+4。由Euler公式|V（G）|-|E（G）|+ |F（G）|=2，得。

定義權(quán)轉(zhuǎn)移規(guī)則如下：

R1：每一個(gè)三面從其相關(guān)點(diǎn)處收獲1/3；

R2：v是與內(nèi)部非三角形面f相關(guān)的頂點(diǎn)：（a）設(shè)d（v）=2，則f給予v點(diǎn)2/3；（b）設(shè)d（v）=3，且v是內(nèi)部點(diǎn)：若v是壞點(diǎn)，則f給予v點(diǎn)2/3，否則f給予v點(diǎn)1/3；（c）設(shè)d（v）≥4：若v是內(nèi)部點(diǎn)且v不與3-面相關(guān)，則f給予v點(diǎn)1/3；若v是內(nèi)部點(diǎn)，v與3-面相關(guān)，且f與這個(gè)3-面相鄰，則f給予v點(diǎn)1/3；若v是外部點(diǎn)，v與3-面相關(guān)，但f與這個(gè)3-面不相鄰，f從v點(diǎn)收獲1/3；

R3：外部面f0給D的每個(gè)點(diǎn)4/3。

記每一個(gè)元素的新權(quán)重為w*（x），其中x∈V（G）∪F（G）。

引理2?v∈V（G），w*（v）≥0。

d（v）=3，若v是外部點(diǎn)，則至多與一個(gè)三面相關(guān)，由R3，v可從外部面得到4/3，由R1，只要給予相關(guān)三面1/3，w*（v）≥3-4+4/3-1/3=0；若v是內(nèi)部點(diǎn)，如果v是壞點(diǎn)，則與v相關(guān)的面中必有兩個(gè)非三角形的面，由R1，R2，w*（v）≥3-4+（2/3）×2-1/3=0，如果v不是壞點(diǎn)，由R2，w*（v）≥3-4+（1/3）×3=0。

d（v）=4，若v是外部點(diǎn)，如果v與一個(gè)三面相關(guān)且三面與D相鄰，則與v相關(guān)的另外兩個(gè)面中一個(gè)與三面相鄰，一個(gè)與三面不相鄰，由R3，一個(gè)面既無收獲也不給予，一個(gè)給予f面1/3，則w*（v）=4-4+4/3-1/3-1/3＞0；如果v與一個(gè)三面相關(guān)且三面不與D相鄰，則與v相關(guān)的另外兩個(gè)面既無收獲也不給予，w*（v）=4-4+4/3-1/3＞0；如果v不與三面相關(guān)，由R3，w*（v）=4-4+4/3＞0；若v不是外部點(diǎn)，如果v與一個(gè)三面相關(guān)，由R1，v要給予相關(guān)三面1/3，而與v相關(guān)的面中除這個(gè)三面外必有三個(gè)非三角形的面，其中兩個(gè)與三面相鄰，一個(gè)不與三面相鄰，由R3，一個(gè)面既無收獲也不給予，兩個(gè)面給予v點(diǎn)各1/3，則w*（v）=4-4-1/3+（1/3）×2＞0，如果v不與三面相關(guān)，w*（v）=4-4=0。

d（v）=5，若v是內(nèi)部點(diǎn)，由R1和R3，v至多給兩個(gè)三面1/3，同時(shí)至多給一個(gè)非三面1/3，w*（v）≥5-4-（1/3）×3=0；若v是外部點(diǎn)，由R1和R3，w*（v）≥5-4+4/3-（1/3）×5＞0。

d（v）≥6，由R1和R3，v至多給d（v）個(gè)1/3，w*（v）≥d（v）-4+d（v）×（1/3）≥0。

引理3w*（f0）＞0。

證明由f0=4，w*（f0）=d（f0）+4-d（f0）×（4/3）＞0。

引理4?f≠f0，w*（f）≥0。

證明d（f）=3，由R1，w*（f）=3-4+3×（1/3）=0。

d（f）＞8，若f與一個(gè)2度點(diǎn)v相鄰，顯然，由R2，f給予v點(diǎn)2/3，且f與D相關(guān)的公共點(diǎn)中有2個(gè)點(diǎn)的度大于等于3，這2個(gè)點(diǎn)也是D邊界上2度點(diǎn)形成的最大路徑的端點(diǎn)，且這2個(gè)點(diǎn)從面既不給予也不收獲，設(shè)由這2個(gè)點(diǎn)劃分的D邊界上的另一段路徑為P，且最多P上的每個(gè)點(diǎn)的度都為3，且都與一個(gè)三角形相鄰，則w*（f）=d（f）-4+（d（f）-2）×（2/3）≥0。

d（f）=6或d（f）=7，若f與一個(gè)2度點(diǎn)v相鄰，顯然，v∈D，則會(huì)出現(xiàn)4-圈與6-圈或7-圈有公共邊的情況，矛盾。故，以下總假設(shè)非外部面上沒有2度點(diǎn)。設(shè)d（f）=6，由于G中的6-面不與三面相鄰，則f最多給予每個(gè)點(diǎn)1/3，則w*（f）≥6-4-6×（1/3）=0，設(shè)d（f）=7，由于G中的7-面不與三面相鄰，則f最多給予每個(gè)點(diǎn)1/3，則w*（f）≥7-4-7×（1/3）＞0。

d（f）=8，分下列情況討論：

（1）若f給其至少4個(gè)點(diǎn)最多都是1/3，或者至少有2個(gè)點(diǎn)從f處既不收獲也不給予，則w*（f）≥8-4-4×（2/3）-4×（1/3）≥0，或者w*（f）≥8-4-6×（2/3）≥0。

（2）若f中有一個(gè)點(diǎn)v∈D，則該點(diǎn)不是壞點(diǎn)，d（v）≥3。若d（v）=3，則該點(diǎn)從f處既不收獲也不給予，且f中與v相鄰的點(diǎn)中也有一個(gè)點(diǎn)屬于D，加上其他的6個(gè)點(diǎn)不可能都是壞點(diǎn)，w*（f）≥8-4-5×（2/3）-2×（1/3）≥0；若d（v）≥4，且v不與三面相關(guān)，則該點(diǎn)從f處既不收獲也不給予，而其他7個(gè)點(diǎn)至少有2個(gè)點(diǎn)不是壞點(diǎn)，w*（f）≥8-4-5×（2/3）-2×（1/3）≥0，若v與三面相關(guān)分以下情況討論：（i）f與三面不相鄰，則f從v收獲1/3，而另外7個(gè)點(diǎn)不可能都是壞點(diǎn)，則w*（f）≥8-4-6×（2/3）-1/3+1/3≥0；（ii）f與三面相鄰，則點(diǎn)v既無收獲也不給予，而另外7個(gè)點(diǎn)不可能都是壞點(diǎn)。若有6個(gè)壞點(diǎn)，必有4個(gè)三角形與f相鄰，另一點(diǎn)u，必然d（u）≥4，則由R2，f從v收獲1/3，則w*（f）≥8-4-6×（2/3）+1/3≥0，若有5個(gè)壞點(diǎn)，則另2個(gè)點(diǎn)最多從f面收獲1/3，則w*（f）≥8－4-5×（2/3）-2×（1/3）≥0，若只有4個(gè)及其以下壞點(diǎn)，則w*（f）≥8－4-4×（2/3）-4×（1/3）≥0。

（3）不妨設(shè)f中的點(diǎn)都不屬于D，且或者有6個(gè)壞點(diǎn)，或者有5個(gè)壞點(diǎn)。若f有6個(gè)壞點(diǎn)，則f必然與四個(gè)三面相鄰，則另2個(gè)點(diǎn)的度大于等于4，則這2個(gè)點(diǎn)給予f面1/3，則w*（f）≥8－4-6×（2/3）+2×（1/3）≥0；若f有5個(gè)壞點(diǎn)，或者f與四個(gè)三面相鄰，則另3個(gè)點(diǎn)的度大于等于4，則這3個(gè)點(diǎn)給予f面1/3，則w*（f）≥8－4-5×（2/3）+3×（1/3）≥0，或者f與三個(gè)三面相鄰，則相關(guān)的6個(gè)點(diǎn)中必有1個(gè)點(diǎn)的度大于等于4，則該點(diǎn)給予f面1/3，則w*（f）≥8－4-5×（2/3）-2×（1/3）+1/3≥0。

d（f）＝9，由于f最多可與4個(gè)三角形相關(guān)，但由于G無四元組，所以不可能有連續(xù)的5個(gè)壞點(diǎn)出現(xiàn)，則8個(gè)公共點(diǎn)中必然有2個(gè)非壞點(diǎn)，則w*（f）≥9－4-6×（2/3）-3×（1/3）≥0。

d（f）＝10，由于f最多可與5個(gè)三角形相關(guān)，但由于G無四元組，所以不可能有連續(xù)的5個(gè)壞點(diǎn)出現(xiàn)，則10個(gè)公共點(diǎn)中必然有2個(gè)非壞點(diǎn)，則w*（f）≥10－4-8×（2/3）-2×（1/3）≥0。

d（f）＝11，由于f最多可與5個(gè)三角形相關(guān)，最多擁有10個(gè)公共點(diǎn)，則剩下的一個(gè)點(diǎn)最多從面收獲1/3，則w*（f）≥11－4-10×（2/3）-1/3≥0。

d（f）≥12，最多f的每個(gè)點(diǎn)都從f面收獲2/3，則w*（f）≥d（f）-4－d（f）×（2/3）≥0。

根據(jù)前述三個(gè)引理，新權(quán)重之和大于零，與歐拉公式矛盾，因此，極小平面圖G不存在。故有：

定理2設(shè)G∈Γ，則G的每一個(gè)4-圈和長(zhǎng)為6至11的圈的3-正常著色φ都可擴(kuò)充到G。

3 定理1的證明

?G∈Γ，如果G中不含4-圈、6-圈和7-圈，則圖G為不含4-7圈的平面圖，由文獻(xiàn)[1]G是3-可著色的。若G有4-圈、6-圈或7-圈，由定理2，則G的每一個(gè)4-圈、6至11-圈的3-正常著色φ都可擴(kuò)充到G，G是3-可著色的。從而定理1得證。

[1]Borodin O V，Glebov A N，Raspaud A，et al.Planar graphs without cycles of length from 4 to 7 are 3-colorable[J].Combin Theroy Ser B，2005，93：303-311.

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

[3]趙春紅，董偉.平面圖3可著色的充分條件[J].南京師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，34（3）：13-18.

[4]趙春紅，蔡宇澤.一類不含5-圈平面圖結(jié)構(gòu)的幾個(gè)結(jié)論[J].沙洲職業(yè)工學(xué)院學(xué)報(bào)，2013，16（2）：30-33.

[5]Lu Xiaoxu，Xu Baogang.A theorem on 3-colorable plane graphs[J].南京師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，29（3）：5-8.

A sufficient condition for 3-colorable plane graphs

ZHAO Chunhong
（Department of Architectural Engineering，Shazhou Professional Institute of Technology，Zhangjiagang 215600，China）

In order to study the 3 coloring problem of plane graphs,this paper uses the method of transferring the right to prove a sufficient condition for 3-colorable plane graphs,i.e.every plane graph without 5-cycles of which each 4,6 or 7-cycles is not adjacent to cycles of length less than 8 is 3-colorable.

plane graph；cycle；coloring

O157.6MR（2000）Subject Classification：05C10

A

1672-0687（2015）01-0020-04

責(zé)任編輯：謝金春

2014-04-09

國(guó)家自然科學(xué)基金資助項(xiàng)目（10926126）

趙春紅（1976-），女，重慶人，講師，碩士，研究方向：圖論與組合優(yōu)化。