,,

(中國礦業(yè)大學 理學院,江蘇 徐州 221008)

0 引言

本文考慮的圖都是簡單的無向有限圖.分別用V(G),E(G),F(G),Δ(G)(簡記為Δ)表示一個平面圖G的點集,邊集,面集,最大度.用dk(v)表示點v的度數(shù)為k的鄰點的個數(shù),dk+(v)表示點v的度數(shù)不小于k的鄰點的個數(shù).G中任意兩個圈(或面),如果它們至少有一條重邊,則稱為相鄰的;G中的任意兩個圈(或面),如果它們關聯(lián)于同一個頂點,則稱為相交的.若存在一個映射φ:E(G)→{1,2,…,k},對G中任意兩條相鄰接的邊e1和e2,有φ(e1)≠φ(e2),則稱G是k-邊可染色的,使得圖G具有k-邊可染色的最小的正整數(shù)k定義為G的邊色數(shù),記作χ′(G).若圖G滿足χ′(G)=Δ(G)稱G為第一類圖,若χ′(G)=Δ(G)+1稱G為第二類圖.若圖G是連通的第二類圖,并且去掉任意邊e∈G后,G-e是第一類圖,則稱G是一個臨界圖.

Vizing[1,2]證明了6≤Δ≤7的簡單平面圖是第一類的.時隔30多年,文[3,4]分別獨立證明了平面圖猜想對Δ=7是正確的.文[5,6]給出了Δ=6的可平面圖是第一類圖的充分條件.對于Δ=5的可平面圖,文[7]證明了,Δ=5且圍長不小于4的可平面圖是第一類圖.文[8]證明了最大度為5,不含四圈且不含五圈的平面圖是第一類的.文[9]證明了Δ=5且沒有相交三角形的可平面圖是第一類圖.文[10]證明了最大度為4是第一類圖的一些充分條件.筆者將證明:Δ=5且沒有六圈的簡單平面圖是第一類的.

1 臨界圖的性質

引理1[2]設G是一個Δ-臨界圖且v∈V(G),那么

1)v至少相鄰2個Δ-點;

2)如果dk(v)≥1,k≠Δ,則dΔ(v)≥Δ-k+1.

引理2[4]設G是一個Δ-臨界圖,xy∈E(G)使得d(x)+d(y)=Δ+2,那么

1)每個v∈N(x,y){x,y}是Δ-點;

2)每個v∈N(N(x,y)){x,y}滿足d(v)≥Δ-1;

3)如果d(x)<Δ,d(y)<Δ,則每個v∈N(N(x,y)){x,y}是Δ-點.

引理3[3]如果G包含3個不同的點s,t,w滿足下列兩個條件,那么G不是一個Δ-臨界圖;

1)t,w∈N(s),且d(w)<2Δ-d(s)-d(t)+2;

2)sw含在至少d(s)+d(t)-Δ-2個三角形中,且t不是這些三角形的頂點.

2 主要結果

定理Δ=5且沒有六圈的簡單平面圖G是第一類的.

證明假設定理不成立,即G是第二類圖.不失一般性,可以假設G是5-臨界簡單圖,那么G顯然是2-連通的.因此G的每個面的邊界是一個圈,且每條邊位于2個不同面的邊界上.由Euler公式進行簡單變換可得

對于任意x∈V(G)∪F(G),定義x的權初值ch(x)為

下面根據(jù)給出的權轉移規(guī)則(Discharging rules),對每一個x∈V(G)∪F(G)的ch(x)進行調整,從而得到新的初值ch′(x).因為權轉移之后始終保證不影響其和式的值,所以有

如果可以證明對于每一個x∈V(G)∪F(G),都有ch′(x)≥0,則與上式矛盾,從而定理得證.

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

(R2)設x,y,z是3-面f的三個不同頂點,且d(x)≤d(y)≤d(z);

(R2-1)若f是(k,5,5)-面,其中k=2,3,4,則y,z分別分值2給f;

(R2-2)若f是(3,4,5)-面,則y,z分別分值2給f;

(R3)設f是4-面;

(R3-1)若f是(k,5,5,5)-面,其中k=2,3,4,則每個5-點分別分值1給f;

(R3-3)若f是(3,4,5,5)-面,則每個4-點和5-點分別分值1給f;

(R4)設f是5-面;

(R6)若5-點v同時關聯(lián)著(3,4,5)和(3,5,5)-面或同時關聯(lián)著兩個(3,5,5)-面時,則其中3-點不能再關聯(lián)5-面,至多關聯(lián)一個4-面,所以此時v從3-點得到1;

圖1 2-點臨界圖

設f是一個度為3的面,則ch(f)=-4.由引理1,2可知,圖G中度為3的面必定是1個(2,5,5),(3,4,5),(3,5,5),或(4+,4+,4+)-面.因此根據(jù)R2和R5可得ch′(f)=-4+4=0.

設f是一個度為4的面,則ch(f)=-3.由引理1,2,3可知,f必定是一個(2,5,5,5),(3,3+,5,5)或(4+,4+,4+,4+)-面.因此,根據(jù)R3可知,它的各個關聯(lián)頂點恰好分值3給f,使得ch′(f)=-3+3=0

設f是一個度為5的面,則ch(f)=-2.由引理1,2,3可知,f必定是一個(2,5,5,5,5),(3,3+,5,5,5),(3,4,5,5,5),或(4+,4+,4+,4+,4+)-面.因此,根據(jù)R4可知,它的各個關聯(lián)頂點至少分值2給f,使得ch′(f)=-2+2=0.

設v是一個度為2的頂點,則ch(f)=-2,由引理1可知,v的兩個鄰點的度均為5.因此ch′(f)=-2+1×2=0

設v是一個度為4的頂點,則ch(f)=3.通過比較R2,R3,R4可知v分值給3-面總比4-面多,v分值給4-面總比5-面多,所以在下面討論的時候,盡量使v關聯(lián)更多的3-面和4-面.

情況2 若v與兩個4-點相鄰,則v的另外兩個鄰點必是5-點.因為v只給(4,4,4)-面和(4,4,5)-面分值,所以考慮v關聯(lián)盡可能多的這兩個面.

情況3 若v與一個4-點,三個5-點相鄰,則v可能關聯(lián)(4,4,5)-面和(4,5,5)-面,且v只給(4,4,5)-面分值.

情況5 若v與2-點相鄰,則v還與4個5-點相鄰.

綜上所述,當G中不含六圈的時候,對于任意的x∈V(G)∪F(G),都有ch′(x)≥0,這就證明了該定理.

[1]Vizing V G.On an estimate of the chromatic index of a p-graph[J].Diskret Analiz,1964,3(1):25-30.

[2]Vizing V G.Critical graphs with given chromatic class[J].Diskret Analiz,1965,5(1):9-17.

[3]Sanders D P,Zhao Y.Planar graphs of maximum degree seven are class 1[J].Combin Theory Ser B,2001,83(2):201-212.

[4]Zhang L M.Every planar with maximum degree 7 is of class 1[J].Graphs Combin,2000,16(4):467-495.

[5]Zhou G F.A note on graphs of class 1[J].Discrete Math,2003,262(1-3):339-345.

[6]Bu Y H,Wang Weifan.Some sufficient conditions for a planar graph of maximum degree six to be class 1[J].Discrete Math,2006,306(13):1440-1445.

[7]Li X C,Luo R.Edge coloring of embedded graphs with large girth[J].Graphs Combin,2003,19(3):393-401.

[8]周正同,苗連英.最大度是5的可平面圖是第一類的充分條件[J].山東大學學報:自然科學版,2010(04):24-27.

[9]陳永珠,王維凡.第一類平面圖的一個充分條件[J].浙江師范大學學報：自然科學版，2007(4):416-420.

[10]倪偉平.最大度是4的可平面圖是第一類的充分條件[J].華東師范:自然科學版,2010(3):85-91.