趙春紅

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

平面圖3可著色的一個充分條件

趙春紅

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

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

平面圖；圈；著色

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

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

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

要證明此結論，需要先討論一類極小平面圖的結構及其存在性。

1 一類極小平面圖的結構討論

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

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

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

（3）D是一個簡單圈，無弦。

（4）G是2連通的。

（5）G的每一個2度點都屬于D，且沒有一個2度點與一個3面相關。

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

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

（8）G中無四元組。

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

引理1G不含有內部4-面。

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

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

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

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

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

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

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

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

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

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

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

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

因此，G中不含有內部4-面。

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

關于極小平面圖G的存在性討論如下：

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

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

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

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

定義權轉移規(guī)則如下：

R1：每一個三面從其相關點處收獲1/3；

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

R3：外部面f0給D的每個點4/3。

記每一個元素的新權重為w*（x），其中x∈V（G）∪F（G）。

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

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

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

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

d（v）≥6，由R1和R3，v至多給d（v）個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與一個2度點v相鄰，顯然，由R2，f給予v點2/3，且f與D相關的公共點中有2個點的度大于等于3，這2個點也是D邊界上2度點形成的最大路徑的端點，且這2個點從面既不給予也不收獲，設由這2個點劃分的D邊界上的另一段路徑為P，且最多P上的每個點的度都為3，且都與一個三角形相鄰，則w*（f）=d（f）-4+（d（f）-2）×（2/3）≥0。

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

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

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

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

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

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

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

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

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

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

定理2設G∈Γ，則G的每一個4-圈和長為6至11的圈的3-正常著色φ都可擴充到G。

3 定理1的證明

?G∈Γ，如果G中不含4-圈、6-圈和7-圈，則圖G為不含4-7圈的平面圖，由文獻[1]G是3-可著色的。若G有4-圈、6-圈或7-圈，由定理2，則G的每一個4-圈、6至11-圈的3-正常著色φ都可擴充到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].南京師范大學學報：自然科學版，2011，34（3）：13-18.

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

[5]Lu Xiaoxu，Xu Baogang.A theorem on 3-colorable plane graphs[J].南京師范大學學報：自然科學版，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

責任編輯：謝金春

2014-04-09

國家自然科學基金資助項目（10926126）

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