不含5-圈的平面圖的無圈邊著色

吳燕青,謝德政,趙燦鳥

(1.山西師范大學數學系,山西臨汾 041000;2.重慶大學數學與統計學院,重慶 401331)

不含5-圈的平面圖的無圈邊著色

吳燕青1,2,謝德政2,趙燦鳥2

(1.山西師范大學數學系,山西臨汾 041000;2.重慶大學數學與統計學院,重慶 401331)

圖G的一個無圈邊著色是一個正常的邊著色且不含雙色的圈.圖G的無圈邊色數是圖G的無圈邊著色中所用色數的最小者.本文用反證法得到了不含5-圈的平面圖G的無圈邊色數的一個上界.

無圈邊著色;無圈邊色數;平面圖

1 引言

本文所考慮的圖都是有限簡單圖.文中未加定義的術語和記號看文獻[1].如果圖G的一個頂點的度為k(至少為k),稱它為G的一個k-頂點(k+-頂點).如果一個圖G的一個面的度為3,稱它為三角形.一個圖G的正常邊著色是一個映射φ:E(G)→{1,…,k},使得對每一對相鄰的邊e1和e2,有φ(e1)/=φ(e2).一個正常的邊著色φ被稱為是無圈的,如果著色φ中不存在雙色的圈.設c:E(G)→{1,…,k}是G的一個無圈邊著色,且C={1,…,k}.圖G的無圈邊色數是G的無圈邊著色中所用色數的最小者,用(G)表示.如果一個圖G能用k種顏色對它進行無圈邊著色,那么稱這種著色為G的無圈邊k-著色.

2001年,文獻[2]提出了無圈邊著色猜想(簡稱AECC):對于任意的圖G,有

2 主要結論

如果d(f)=4,那么w′(f)=w(f)=0.如果d(f)≥6.根據(R1),顯然w′(f)≥0.

因此,對于x∈V(G)∪F(G),有w′(x)≥0.引理1.1成立.

為了敘述方便,給出以下定義和記號.關于G的一個部分著色c,顏色α∈C對于某條邊e稱為是候選的,如果e的鄰沒有被著顏色α.我們用Rc(e)表示在著色c下由邊e的候選顏色組成的集合.關于G的一個部分著色c,如果一條路上所著的顏色是由α,β交替出現的最長路,稱這條路為(α,β)-最長路.如果一條(α,β)-最長路且它的起點v關聯的邊和終點u關聯的邊所著色的顏色都是α,則稱這條路為(α,β,vu)-關鍵路.對uv∈E(G),C(v)表示與頂點v相關聯的邊在著色c下所著的顏色組成的集合.c(uv)表示uv在著色c下所著的顏色.設Cuv=C(v)-c(uv).如果一個集合S的任何元素在這個集合中可以出現多次并且計算它的元素個數時按重數計算,稱S為多重集(multiset)[5].對于x∈S,用DS(x)表示x在多重集S中出現的次數,用‖S‖表示S的元素個數.設S和S′是兩個多重集,如果一個多重集S?S′包含S與S′中的所有元素且對于x∈S?S′,稱之為S和S′的并.

引理1.2[3]假設顏色α和β是圖G的一個正常邊著色c中的任意兩種不同的顏色,那么G中最多有一條(α,β)-最長路包含某一頂點v.

引理1.3[3]設u,i,j,a,b∈V(G),ui,uj,ab∈E(G)且{λ,ξ}?C,使得

在G的一個部分無圈著色c下,假設存在一條(λ,ξ,ab)-關鍵路包含頂點u，著色c′是在c下交換邊ui和uj的顏色而其它邊的顏色保持不變得到的.如果c′是一個正常的邊著色,那么圖G在c′下就不再存在任何的(λ,ξ,ab)-關鍵路.

定理1.1假設圖G是一個不含5-圈的平面圖,那么χ′a(G)≤Δ(G)+4.

證明假設不成立.設G是含邊數最少的一個反例.顯然G是連通的且δ(G)≥2.根據引理1.1,G至少包含(A1)-(A3)中的一種結構.設k=Δ(G)+4.設顏色集C為:

情形1G包含一個3-頂點v,設{v1,v2,v3}=NG(v),其中

設H=G-vv1,由G的最小性,H有一個無圈邊著色c用了k種顏色.假設d(v1)=5.

情形1.1|C(v)∩C(v1)|=0.

由于

所以存在一種顏色α∈C-C(v)∪C(v1),用它給邊vv1著色而其它邊的顏色保持不變得到著色c′.顯然c′是G的一個無圈邊k-著色,矛盾.

情形1.2|C(v)∩C(v1)|=1.

設v′1是v1在H中的一個鄰,不失一般性,假設c(vv3)=c(v1v′1)=1,c(vv2)=2.不妨設C(v1)={1,3,4,5}.則

否則vv1可著{6,7,…,Δ+4}中的一種顏色而其它邊的顏色保持不變得到G的一個無圈邊k-著色.此時vv3著3,v1v′1著2和vv1著1而其它邊的顏色保持不變得到G的一個無圈邊k-著色,矛盾.

情形1.3

不妨設C(v1)={1,2,3,4}.則{5,6,…,Δ+4}中有一種顏色不在C(v3)中,不妨設5/∈C(v3),用5給vv1著而其它邊的顏色保持不變得到G的一個著色c′.如果c′是G的一個無圈邊k-著色,矛盾.否則,存在一條(1,5,vv1)-關鍵路關于著色c.現在重新著vv3用5而其它邊的顏色保持不變得到著色c′,根據引理1.2,不再有(1,5,vv3)-關鍵路關于著色c′.顯然著色c′是H的一個無圈邊k-著色,正如情形1.2,矛盾.

設ui∈NH(v1),其中i=1,2,3.設Sv是一個多重集且Sv=Cvv2?Cvv3?Cvv4.

情形2.1|C(v)∩C(v1)|=0.

由于|C(v)∪C(v1)|≤3+Δ(G)-1＜k,所以存在α∈C-C(v)∪C(v1),用它給邊vv1著色而其它邊的顏色保持不變得到著色c′,顯然c′是G的一個無圈邊k-著色,矛盾.

情形2.2|C(v)∩C(v1)|=1.

不失一般性,假設c(vv4)=c(v1u1)=1.c(vv2)=2,c(vv3)=3.不妨設C(v1)={1,4,5}.則

否則vv1可著{6,7,…,Δ+4}中的一種顏色而其它邊的顏色保持不變得到G的一個無圈邊k-著色.此時vv4著4,v1u1著2和vv1著1而其它邊的顏色保持不變得到G的一個無圈邊k-著色,矛盾.

如果存在α∈Rc(vv1),用它給邊vv1著色而其它邊的顏色保持不變得到G的一個無圈邊k-著色,矛盾.否則,存在一條(1,α,vv1)-關鍵路或(2,α,vv1)-關鍵路關于著色c.如果在C(v)中至少有兩種顏色在Sv中.由于

因此存在γ∈Rc(vv1)在Sv中出現恰好一次.假設γ∈C(v3),現在用γ給vv4重新著色而其它邊的顏色保持不變得到著色c′,如果c′是H的一個無圈邊著色,那么|C′(v)∩C′(v1)|=1.這種情況前面已討論,矛盾.如果著色c′不是H的一個無圈邊著色,顯然c′是H的一個正常的邊著色且存在一條(1,γ,vv4)-關鍵路關于著色c.但還存在(1,γ,vv1)-關鍵路關于著色c,根據引理1.2,矛盾.如果C(v)中至多有一種顏色在Sv中.假設c(vv4)∈Sv.現在交換邊vv2和vv3的顏色而其它邊的顏色保持不變得到著色c′,顯然c′是H的一個無圈邊著色.設C1表示由邊vv1的候選顏色組成的集合使得它們中的任何一種顏色給邊vv1著和顏色1形成關鍵路.C2與C1類似.根據引理1.3,對于α∈C1不會再存在一條(1,α,vv1)-關鍵路關于著色c′.如果存在α∈C1,用它給邊vv1著色而其它邊的顏色保持不變得到G的一個無圈邊k-著色,矛盾.否則,C1?C′vv4.因而(C1∪C2)?C′vv4,但是|C1∪C2|=Δ(G),這與|C′vv4|≤Δ(G)-1矛盾.

不妨設c(vv2)=1,c(vv3)=2,c(vv4)=3.顯然|Rc(vv1)|=k-3=Δ(G)+1.如果存在α∈Rc(vv1),用它給邊vv1著色而其它邊的顏色保持不變得到G的一個無圈邊k-著色,矛盾.否則,存在一條(1,α,vv1)-關鍵路或(2,α,vv1)-關鍵路或(3,α,vv1)-關鍵路關于著色c.由于‖Sv‖=d(v2)-1+d(v3)-1+d(v4)-1≤2Δ(G)+1,顯然存在一種顏色α∈Rc(vv1)在Sv中恰好出現一次.假設α∈C(v4).現在用顏色α給邊vv3重新著色而其它邊的顏色保持不變得到著色c′.如果c′是H的一個無圈邊著色,那么|C′(v)∩C′(v1)|=2,這種情形前面已討論,矛盾.如果c′不是H的一個無圈邊著色,顯然c′是H的一個正常的邊著色且存在一條(3,α,vv3)-關鍵路關于著色c,但是,關于著色c還存在一條(3,α,vv1)-關鍵路,根據引理1.2,矛盾.

下面假設G不包含結構(A 2)和(A 3),根據引理1,那么G一定包含結構(A 1).

情形3G包含一個2-頂點v,設{v1,v2}=NG(v),其中d(v1)≤d(v2).

現在把G的所有2-頂點刪掉得到圖G′.不失一般性,假設δ(G′)≥2.根據引理1.1,那么G′一定包含(A1)-(A3)中的一種結構,也就是說存在頂點v′∈V(G′),它在G中不滿足(A 1)-(A 3)中的任何一種結構,而在G′中滿足(A 1)-(A 3)中的一種.設

設u是M中度最小的一個頂點.顯然,dG′(u)≤5.設N′(u)={x|x∈NG(u),dG(x)=2}, N′′(u)=NG(u)-N′(u).顯然N′′(u)=NG′(u).根據對u的選擇,|N′(u)|/=0,因此存在u′∈N′(u).設NG(u′)={u,u′′}且H=G-{uu′}.根據對G的選擇,H有一個無圈邊k-著色c.設B′(u)={c(ux)|x∈N′(u)},B′′(u)={c(ux)|x∈N′′(u)}.

由于|C-C(u)∪C(u′)|≥k-(Δ(G)-1+1)=4,所以存在α∈C-C(u)∪C(u′),用它給邊uu′著色而其它邊的顏色保持不變得到G的一個無圈邊k-著色,矛盾.

因此存在α∈C-C(u)∪C(u1),用它給邊uu′著色其它邊的顏色保持不變得到G的一個無圈邊k-著色,矛盾.如果u1∈N′′(u),下面分兩種情況來討論.

(1)如果dG′(u)≤4,由于

所以存在α∈C-B′′(u)∪C(u′′),用它給邊u′u′′重新著色而其它邊的顏色保持不變得到著色c′.顯然c′是H的一個無圈邊著色.如果|C′(u)∩C′(u′)|=0,這種情形前面已討論,矛盾.

如果|C′(u)∩C′(u′)|=1,那么一定存在一個2-頂點u2∈NH(u)且c′(uu2)=c′(u′u′′).這種情形前面已討論,矛盾.

(2)如果dG′(u)=5,那么一定存在一個3-頂點y,它與u相鄰并且在G中不與2-頂點相鄰(在G中不含(A2),而在G′中含(A2)).如果u1=y,由于

因此存在α∈C-C(u)∪C(u1),用它給邊uu′著色而其它邊的顏色保持不變得到G的一個無圈邊k-著色,矛盾.如果u1/=y,由于

所以存在α∈C-C(u′′)∪B′′(u)c(uy),用它給邊u′u′′重新著色而其它邊的顏色保持不變得到著色c′.顯然c′是H的一個無圈邊著色.如果|C′(u)∩C′(u′)|=0,這種情形前面已討論,矛盾.如果|C′(u)∩C′(u′)|=1,那么一定存在一個2-頂點u2∈NH(u)且c′(uu2)=c′(u′u′′)或者c′(u′u′′)=c′(uy).這種情形前面已討論,矛盾.

[1]Bondy J A,Murty U SR.Graph Theory with App licattion[M].New York:Macm illan Press,1976.

[2]A lon N,Sudakov B,Zaks A.Acyclic edge colorings of graphs[J].J.Graph Theory,2001,37:157-167.

[3]Basavaraju M,Sunil Chand ran L.Acyclic edge coloring of graphs with m aximum degree 4[J].J.Graph Theory,2009,61:192-209.

[4]Hou J,Wu J,Liu G,et al.Acyclic edge colorings of p lanar graphs and series-parallel graphs[J].Science in China Series A:Mathem atics,2009(3):605-616.

[5]Basavara ju M,Sunil Chandran L.Acyclic edge coloring of p lanar graphs[J].SIAMJ.Discrete Math., 2011,25:463-478.

[6]Dong W,Xu B.Some resu lts on acyclic edge colorings of p lanar graphs[J].Information Processing Letters, 2010,110:887-892.

[7]Borow ieckiM,Fiedorow icz A.Acyclic edge coloring of p lanar graphswithout short cycles[J].Discrete Math., 2010,310:1445-1455.

A cyclic edge coloring of planar graphs without 5-cycles

Wu Yanqing1,2,Xie Dezheng2,Zhao Canniao2
(1.Departm ent of Mathem atics,Shanxi Norm al University,Lin fen 041000,China; 2.College of Mathem atics and Statistics,Chongqing University,Chongqing 401331,China)

An acyclic edge coloring of a graph Gis a proper edge coloring such that there are no bichrom atic cycles.The acyclic edge chromatic number of a graph Gis the least number of colors in an acyclic edge coloring of G.In this paper,an upper bound on the acyclic edge chrom atic number for p lanar graphs without 5-cycles was obtained using p roof of contradiction.

acyclic edge coloring,acyclic edge chromatic number,p lanar graph

O157.5

A

1008-5513(2012)03-0342-07

2010-10-22.

吳燕青(1982-),碩士,助教,研究方向：圖論及其應用.

2010 MSC:05C15