不含4-圈和5-圈的平面圖的非正常2-染色的一個新結果

周倩倩,孫磊

(山東師范大學數學與統計學院,山東 濟南 250014)

1 引言

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

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

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

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

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

2 定理1.2的證明

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

2.1 結構分析

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

引理 2.1δ(G)≥2.

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

引理 2.2每個18?-點至少有一個19+-鄰點.

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

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

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

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

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

引理 2.5每個19-點,至少有一個9+-鄰點.

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

下面是將用到的兩個簡單的結果.

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

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

2.2 權轉移

為完成定理1.2的證明,將利用上述性質通過權轉移方法導出矛盾.

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

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

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

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

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

(R3)每個7-面,若7-面中含有2-度點,且鄰接3-圈,則給每個關聯的3-圈若 7-面中不含有2-度點,且鄰接3-圈,則給每個關聯的3-圈

(R4)每個8+-面給每個關聯的3-圈

(R5)每個1118-點v給每個關聯的3?-點若v所關聯的 3?-點的個數小于d(v)?1,則v將多余權值轉移至所關聯的67-面.

(R6)每個 19+-點給每個關聯的3?-點

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

v為G中任意一個點.

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

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

如果d(v)=410,顯然ch′(v)≥0,因為由上述權轉移規則,此類點既不接受權值也不給予權值.

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

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

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

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

f為G中任意一個圈,下面檢驗圈的權值.

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

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

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

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

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

(b)若鄰接1個2-點,因為不含5-圈,最差的情況為鄰接4個3-圈,如圖1中的(3),則與 (1)類似,由(R1),(R5)得,

(c)若鄰接 2個 2-點,因為不含 5-圈,最差的情況為鄰接 2個 3-圈,如圖 1中的 (4),由 (R1)得,

(d)若鄰接3個 2-點,因為不含5-圈,由觀察2,此時不鄰接 3-圈,由(R1)得,

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

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

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

若鄰接 1個 2-點,因為不含 5-圈,最差的情況為鄰接 6個 3-圈,如圖 1中的 (6),則由 (R1),(R5)得,

若鄰接2個2-點,因為不含5-圈,最差的情況為鄰接 4個3-圈,如圖1中的(7),則由 (R1)可得,

注 2.1因為不含4-圈和5-圈,所以不會同時出現兩個及以上鄰著2-點的3-圈.

若鄰接 3個 2-點,因為不含 5-圈,最差的情況為鄰接 2個 3-圈,如圖 1中的 (8),則由 (R1)得,

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

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

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

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

圖1 圈的權值圖

[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.