不含5-圈的平面圖的無(wú)圈邊著色

吳燕青,謝德政,趙燦鳥(niǎo)

(1.山西師范大學(xué)數(shù)學(xué)系,山西臨汾 041000;2.重慶大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,重慶 401331)

不含5-圈的平面圖的無(wú)圈邊著色

吳燕青1,2,謝德政2,趙燦鳥(niǎo)2

(1.山西師范大學(xué)數(shù)學(xué)系,山西臨汾 041000;2.重慶大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,重慶 401331)

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

無(wú)圈邊著色;無(wú)圈邊色數(shù);平面圖

1 引言

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

2001年,文獻(xiàn)[2]提出了無(wú)圈邊著色猜想(簡(jiǎn)稱AECC):對(duì)于任意的圖G,有

2 主要結(jié)論

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

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

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

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

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

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

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

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

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

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

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

由于

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

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

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

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

情形1.3

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

設(shè)ui∈NH(v1),其中i=1,2,3.設(shè)Sv是一個(gè)多重集且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的一個(gè)無(wú)圈邊k-著色,矛盾.

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

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

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

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

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

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

下面假設(shè)G不包含結(jié)構(gòu)(A 2)和(A 3),根據(jù)引理1,那么G一定包含結(jié)構(gòu)(A 1).

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

現(xiàn)在把G的所有2-頂點(diǎn)刪掉得到圖G′.不失一般性,假設(shè)δ(G′)≥2.根據(jù)引理1.1,那么G′一定包含(A1)-(A3)中的一種結(jié)構(gòu),也就是說(shuō)存在頂點(diǎn)v′∈V(G′),它在G中不滿足(A 1)-(A 3)中的任何一種結(jié)構(gòu),而在G′中滿足(A 1)-(A 3)中的一種.設(shè)

設(shè)u是M中度最小的一個(gè)頂點(diǎn).顯然,dG′(u)≤5.設(shè)N′(u)={x|x∈NG(u),dG(x)=2}, N′′(u)=NG(u)-N′(u).顯然N′′(u)=NG′(u).根據(jù)對(duì)u的選擇,|N′(u)|/=0,因此存在u′∈N′(u).設(shè)NG(u′)={u,u′′}且H=G-{uu′}.根據(jù)對(duì)G的選擇,H有一個(gè)無(wú)圈邊k-著色c.設(shè)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的一個(gè)無(wú)圈邊k-著色,矛盾.

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

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

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

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

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

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

所以存在α∈C-C(u′′)∪B′′(u)c(uy),用它給邊u′u′′重新著色而其它邊的顏色保持不變得到著色c′.顯然c′是H的一個(gè)無(wú)圈邊著色.如果|C′(u)∩C′(u′)|=0,這種情形前面已討論,矛盾.如果|C′(u)∩C′(u′)|=1,那么一定存在一個(gè)2-頂點(diǎn)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-),碩士,助教,研究方向：圖論及其應(yīng)用.

2010 MSC:05C15