周倩倩,孫磊

(山東師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,山東 濟(jì)南 250014)

1 引言

先定義一些概念,本文中所考慮的圖是有限,簡單,無向圖.稱圖G=(V,E)是可平面的,如果它能被嵌入一個平面使得邊僅在端點(diǎn)處相交.可平面圖在平面內(nèi)的一個嵌入叫平面圖.對于平面圖G,用V,E,F,?,δ,分別表示平面圖G的頂點(diǎn)集,邊集,面集,最大度,最小度.對任意一個頂點(diǎn)v∈V,用d(v)表示v在G中的度數(shù),即與v相關(guān)聯(lián)的邊的條數(shù).如果相應(yīng)地有d(v)=k,d(v)≥k,d(v)≤k,稱v分別為k-點(diǎn),k+-點(diǎn),k?-點(diǎn).對于面f∈F,用d(f)表示f的邊界的長度,稱為面f的度.稱f分別為k-面,k+-面,k?-面,如果相應(yīng)地有d(f)=k,d(f)≥k,d(f)≤k.一個k-圈是一個長度為k的圈,3-圈又叫作三角形.稱兩個圈鄰接,若它們至少有一條公共邊.令v∈V,稱v為一個ij-點(diǎn),若i≤d(v)≤j.一個圖的圍長指的是這個圖中最短圈的長度.另外,圖中的實(shí)點(diǎn)表示度數(shù)已經(jīng)確定,虛點(diǎn)的度數(shù)尚未確定.更多的術(shù)語可見文獻(xiàn)[1].

設(shè)d1,d2,···,dk是k個非負(fù)整數(shù),若圖G=(V,E)的頂點(diǎn)集V能被剖分成k個子集V1,···,Vk,使得對任意的i=1,···,k,Vi的點(diǎn)導(dǎo)出子圖G[Vi]的最大度至多為di,則稱圖G是非正常 (d1,d2,···,dk)-可染的,簡稱 (d1,d2,···,dk)-可染的.用這個概念,著名的四色定理可敘述為:每個平面圖是(0,0,0,0)-可染的,見文獻(xiàn)[2-3].對于一個(d1,d2,d3)-可染的平面圖,已有一些結(jié)果是通過禁掉某些圈,得到一些充分條件,見文獻(xiàn)[4-5].而我們將目標(biāo)轉(zhuǎn)移到研究平面圖非正常染色的最簡單的形式,即用兩種顏色來染平面圖.另外還有許多文章研究圍長g≥6,見文獻(xiàn)[6-8].令?g表示圍長至少為g的平面圖類,文獻(xiàn)[9]構(gòu)造出一個在?4中不能(d1,d2)-可染的圖,而且在圍長的限制下,有以下結(jié)果:

定理 1.1圍長至少為5的平面圖為(2,6),(4,4),(3,5)-可染的[6,10-11].

基于上述結(jié)果,我們將不再限制圍長,而是禁掉4-圈和5-圈,保留3-圈,得到的主要結(jié)果如下:

定理 1.2既不含4-圈又不含5-圈的平面圖是(9,9)-可染的.

2 定理1.2的證明

假設(shè)定理1.2不成立,設(shè)G=(V,E)為定理1.2的一個點(diǎn)極小反例.顯然G是2-連通的,將G嵌入平面,得到一個平面圖G=(V,E,F),其中F為G的面的集合.因?yàn)镚中不含4-圈,所以G不含相鄰三角形,我們先來研究G的結(jié)構(gòu)特征.

2.1 結(jié)構(gòu)分析

說正常染好一個點(diǎn)v是指用一個未曾用在v的任何鄰點(diǎn)上的色去染v.對于一個圖G=(d1,d2),令φ=1,2表示顏色集,若φ(v)=i,且v關(guān)聯(lián)di個染顏色i的鄰居,則稱點(diǎn)v為一個i-飽和點(diǎn).

引理 2.1δ(G)≥2.

證明假設(shè)G有一個1-點(diǎn),由G的極小性,G-v有一個(9,9)-染色φ,因?yàn)関為1-點(diǎn),所以v的鄰點(diǎn)至多用了一種顏色,因此v可正常染好,從而得到G的一個(9,9)-染色,這與G的選取相矛盾.

引理 2.2每個18?-點(diǎn)至少有一個19+-鄰點(diǎn).

證明反證法.假設(shè)v為一個18?-點(diǎn),且v的每個鄰居的度至多為18,由G的極小性,G-v有一個(9,9)-染色φ=1,2,顯然,v的鄰居中兩種顏色必須都出現(xiàn),不然,很容易將G染回.不失一般性,若v至多9個鄰居染2,則可先讓v染2,若不能得到G的一個(9,9)-染色,則說明染2的v的鄰居中至少有一個2-飽和點(diǎn),重染這些2-飽和點(diǎn)為1,因?yàn)関的鄰居的度都至多為18,所以可重染為1,這樣v可染2,從而得到G的一個染色,矛盾.

引理 2.3若v為G的一個2-點(diǎn),則v鄰著一個11+-點(diǎn),一個19+-點(diǎn).

證明首先由文獻(xiàn)[10]中的引理2.1可知,對于G=(9,9)中的二度點(diǎn),此二度點(diǎn)鄰著兩個 11+-點(diǎn),又由上面的引理 2.2可知,每個18?-點(diǎn)至少有一個19+-鄰點(diǎn),所以G的一個2-點(diǎn),鄰著一個11+-點(diǎn),一個19+-點(diǎn).

引理 2.4若v為G的一個3-點(diǎn),則v至少鄰著一個11+-點(diǎn),一個19+-點(diǎn).

證明首先由文獻(xiàn)[10]中的引理2.2可知,對于G=(9,9)中的三度點(diǎn),此三度點(diǎn)至少鄰著兩個11+-點(diǎn),又由上面的引理2.2可知,每個18?-點(diǎn)至少有一個 19+-鄰點(diǎn),所以G的一個 3-點(diǎn),至少鄰著一個11+-點(diǎn),一個19+-點(diǎn).

引理 2.5每個19-點(diǎn),至少有一個9+-鄰點(diǎn).

證明反證法.假設(shè)v為一個19-點(diǎn),且v的每個鄰居的度至多為8,由G的極小性,G-v有一個(9,9)-染色φ=1,2,顯然,v的鄰居中兩種顏色必須都出現(xiàn),不然,很容易將G染回.不失一般性,若v至少10個鄰居染2,則可先讓v染1,若不能得到G的一個(9,9)-染色,則說明染2的v的鄰居中至少有一個2-飽和點(diǎn),因?yàn)関的鄰居的度都至多為8,所以不會出現(xiàn)1-飽和點(diǎn),同樣類似也不會出現(xiàn)2-飽和點(diǎn),這樣v可染好,從而得到G的一個染色,矛盾.

下面是將用到的兩個簡單的結(jié)果.

觀察 2.1每個 6+-圈,至多鄰?d(f)/2?個 2-點(diǎn).

觀察 2.2若v為G的一個2-點(diǎn),則此2-點(diǎn)不會同時鄰接3-圈和6-圈.

2.2 權(quán)轉(zhuǎn)移

為完成定理1.2的證明,將利用上述性質(zhì)通過權(quán)轉(zhuǎn)移方法導(dǎo)出矛盾.

顯然定理1.2的點(diǎn)極小反例G=(V,E,F)是2-連通的,因此G中每個面的邊界是一個圈.定義初始權(quán)ch(x)=d(x)?4,x∈V∪F,由握手定理和歐拉公式|V(G)|?|E(G)|+|F(G)|=2,有

通過重新定義權(quán)轉(zhuǎn)移法則,重新分配點(diǎn)和面的權(quán),使對每個x∈V∪F,有ch′(x)≥0,則得矛盾,

下面來證對每個x∈V∪F,ch′(x)≥0得到矛盾.權(quán)值轉(zhuǎn)移規(guī)則如下:

(R1)每個 6+-面給它的每個3?-鄰點(diǎn)

(R2)每個6-面給每個含2-度點(diǎn)的3-圈給每個不含2-度點(diǎn)的3-圈

(R3)每個7-面,若7-面中含有2-度點(diǎn),且鄰接3-圈,則給每個關(guān)聯(lián)的3-圈若 7-面中不含有2-度點(diǎn),且鄰接3-圈,則給每個關(guān)聯(lián)的3-圈

(R4)每個8+-面給每個關(guān)聯(lián)的3-圈

(R5)每個1118-點(diǎn)v給每個關(guān)聯(lián)的3?-點(diǎn)若v所關(guān)聯(lián)的 3?-點(diǎn)的個數(shù)小于d(v)?1,則v將多余權(quán)值轉(zhuǎn)移至所關(guān)聯(lián)的67-面.

(R6)每個 19+-點(diǎn)給每個關(guān)聯(lián)的3?-點(diǎn)

現(xiàn)在來驗(yàn)證對每個元素x∈V∪F,ch′(x)≥0.

v為G中任意一個點(diǎn).

如果d(v)=2,顯然ch(v)=?2.由前面的引理,v至少關(guān)聯(lián)1個1118-點(diǎn)和1個19+-點(diǎn),由 (R1),(R5),(R6)可得,

如果d(v)=3,顯然ch(v)=?1.由前面的引理,v至少關(guān)聯(lián)1個1118-點(diǎn)和1個19+-點(diǎn),由 (R1),(R5),(R6)可得,

如果d(v)=410,顯然ch′(v)≥0,因?yàn)橛缮鲜鰴?quán)轉(zhuǎn)移規(guī)則,此類點(diǎn)既不接受權(quán)值也不給予權(quán)值.

如果d(v)=1118,最差的情況為11-點(diǎn)的情況.由前面的引理,v至少關(guān)聯(lián)1個19+-點(diǎn),由 (R5)可得,

如果d(v)=19,由前面的引理,v至少關(guān)聯(lián)1個9+-點(diǎn),由(R6)可得,

如果d(v)=20,由 (R6)可得,

如果d(v)≥21,最差的情況為21-點(diǎn)的情況.由(R6)可得,

f為G中任意一個圈,下面檢驗(yàn)圈的權(quán)值.

如果d(f)=3,ch(f)=?1,下面分為兩種情況討論:

若3-圈中有2-點(diǎn),根據(jù)前面觀察1,則此3-圈至少鄰接一個7+-面,一個6+-面,如圖1中的(1).如果鄰接7-面,則此7-面中含2-點(diǎn),由(R2),(R3),(R4)可得,

若3-圈中不含有2-點(diǎn),則此3-圈至少鄰接三個6+-面,則由(R2),(R3),(R4)可得,

如果d(f)=6,ch(f)=2,最差的情況為鄰接含有2-點(diǎn)的3-圈.

(a)鄰接6個含2-點(diǎn)的3-圈,如圖1中的(2),則由前面的引理,每個2-點(diǎn)所鄰的度數(shù)較小的11+-點(diǎn)會至少鄰接為2個19+-點(diǎn),所以至少會多出的權(quán)值,由(R1),(R5)得,

(b)若鄰接1個2-點(diǎn),因?yàn)椴缓?-圈,最差的情況為鄰接4個3-圈,如圖1中的(3),則與 (1)類似,由(R1),(R5)得,

(c)若鄰接 2個 2-點(diǎn),因?yàn)椴缓?5-圈,最差的情況為鄰接 2個 3-圈,如圖 1中的 (4),由 (R1)得,

(d)若鄰接3個 2-點(diǎn),因?yàn)椴缓?-圈,由觀察2,此時不鄰接 3-圈,由(R1)得,

如果d(f)=7,ch(f)=3,類似于上述分析:

(a)鄰接7個3-圈,這種情況下7-圈中無2-點(diǎn),如圖1中的(5),都為4+-點(diǎn),則由 (R3)可得,

(b)若7-圈中含有2-點(diǎn),類似于6-圈的分析,分為以下幾種情況:

若鄰接 1個 2-點(diǎn),因?yàn)椴缓?5-圈,最差的情況為鄰接 6個 3-圈,如圖 1中的 (6),則由 (R1),(R5)得,

若鄰接2個2-點(diǎn),因?yàn)椴缓?-圈,最差的情況為鄰接 4個3-圈,如圖1中的(7),則由 (R1)可得,

注 2.1因?yàn)椴缓?-圈和5-圈,所以不會同時出現(xiàn)兩個及以上鄰著2-點(diǎn)的3-圈.

若鄰接 3個 2-點(diǎn),因?yàn)椴缓?5-圈,最差的情況為鄰接 2個 3-圈,如圖 1中的 (8),則由 (R1)得,

注 2.2類似于上述情況的說明,最差只能鄰接1個3-圈.

如果d(f)=8,ch(f)=4,由前面的觀察2可知至多鄰4個2-點(diǎn),又由(R1),(R4)可知,3-圈和2-點(diǎn)都會從8-圈中得到的權(quán)值,所以類似于上述分析,有

如果d(f)≥9,ch(f)≥5,由前面的觀察 2可知至多鄰?d(f)/2?個 2-點(diǎn),根據(jù)注 2.1和注 2.2,且肯定鄰接少于d(f)??d(f)/2?個 3-圈,則由 (R1),(R4)可知即證.

于是移值后,在任何一種情況下,對每個元素x∈V(G)∪F(G),有ch′(x)≥0,所有點(diǎn)數(shù)值和這與矛盾,從而完成定理1.2的證明.

圖1 圈的權(quán)值圖

[1]Bollobas B.Modern Graph Theory[M].New York:Springer-Verlag,1998.

[2]Appel K,Haken W.Every planar graph map is four colorable part I:Discharging[J].Illinois J.Math.,1977,21:429-490.

[3]Appel K,Haken W.Every planar graph map is four colorable part II:Reducibility[J].Illinois J.Math.,1977,21:491-567.

[4]Xu L,Miao Z,Wang Y.Every planar graph with cycles of length neither 4 nor 5 is(1,1,0)-colorable[J].J.Comb.Optim.,2014(28):774-786.

[5]Hill O,Smith D,Wang Y,et al.Planar graphs without 4-cycles or 5-cycles are(3,0,0)-colorable[J].Discrete Mathematics,2013,313(20):2312-2317.

[6]Borodin O V,Kostochka A V.Defective 2-coloring of sparse graph[J].J.Combin.Theory Ser.B.,2014,104:72-80.

[7]Borodin O V,Kostochka A V,Yancey M.On 1-improper 2-coloring of sparse graphs[J].Discrete Mathematics,2013,313(22):2638-2649.

[8]Borodin O V,Kostochka A V.Vertex decompositions of sparse graphs into an independent set and a subgraph of maximum degree at most 1[J].Sibirsk.Mat.Zh,2011,52(5):1004-1010.

[9]Montassier M,Ochem P.Near-colorings:non-colorable graphs and np-completeness[J].The Electric Journal of Combinatorics,2015,22(1):1-57.

[10]Choi I,Raspaud A.Planar graphs with girth at least 5 are(3,5)-colorable[J].Discrete Mathematics.2015,338:661-667.

[11]Havet F,Sereni J S.Improper choosability of graphs and maximum average degree[J].J.Graph.Theory.2006,52:181-199.