最大度為4的外平面圖的無圈邊色數(shù)*

王藝橋, 舒巧君

(1.北京中醫(yī)藥大學(xué) 管理學(xué)院,北京 100029;2.杭州電子科技大學(xué) 理學(xué)院,浙江 杭州 310018)

本文僅考慮有限簡(jiǎn)單圖.給定一個(gè)圖G,用V(G),E(G)和Δ(G)分別表示它的頂點(diǎn)集、邊集和最大度.圖G的正常k-邊染色是指映射c：E(G)→{1,2,…,k},使得相鄰的邊染不同的顏色;若G有一個(gè)k-邊染色,則稱圖G是k-邊可染的;邊色數(shù)χ′(G)是指使得圖G是k-邊可染的最小整數(shù)k;無圈k-邊染色是指圖G的一個(gè)正常的k-邊染色,使得任一個(gè)圈上至少有3種不同的顏色;無圈邊色數(shù)a′(G)是指使得圖G是無圈k-邊染色的最小整數(shù)k.

若無混淆,下文均將Δ(G)簡(jiǎn)記為Δ.根據(jù)Vizing定理[1],Δ≤χ′(G)≤Δ+1.顯然,Δ≤χ′(G)≤a′(G).

猜想1對(duì)任意圖G,a′(G)≤Δ+2.

猜想1至今尚未得到證實(shí),但對(duì)一些特殊圖已被證明猜想1成立.Alon等[6]證明了確定一個(gè)圖G的無圈邊色數(shù)是一個(gè)NP-問題.關(guān)于完全二部圖、最大度為3的圖及最大度為4的圖的無圈邊色數(shù)的研究可參見文獻(xiàn)[7-9].對(duì)于平面圖G,Basavaraju等[10]證明了a′(G)≤Δ+12;后來文獻(xiàn)[11]將上界Δ+12降到Δ+7.

若圖G存在一個(gè)平面嵌入,使得它的所有頂點(diǎn)在一個(gè)面的邊界上出現(xiàn),則稱G為外平面圖.令H2n表示在2n-圈x1x2…x2nx1上添加n-1條弦x2x2n,x3x2n-1,…,xnxn+2后所得的圖,Q表示在7-圈y1y2…y7y1上加弦y2y7,y2y6,y3y5,y3y6后所得到的圖,如圖1所示.

圖1 圖H2n,Q,S1和S2

設(shè)G是一個(gè)外平面圖.2007年,Muthu等[12]證明了a′(G)≤Δ+1.文獻(xiàn)[13]改進(jìn)了這個(gè)結(jié)果,即證明了：當(dāng)Δ≥5 時(shí),a′(G)=Δ;當(dāng)Δ=3且G是2-連通時(shí),a′(G)=4當(dāng)且僅當(dāng)G含有與H2n同構(gòu)的子圖.此外,文獻(xiàn)[13]還斷言:若Δ=4,則4≤a′(G)≤5,且a′(G)=5當(dāng)且僅當(dāng)G含有與Q同構(gòu)的子圖.然而,這個(gè)結(jié)論是不正確的.事實(shí)上,王維凡等(在一篇未發(fā)表的論文中)構(gòu)造出圖S1和S2有a′(S1)=a′(S2)=5,但S1和S2均不含與Q同構(gòu)的子圖,如圖1所示.

本文旨在給出一個(gè)最大度為4的外平面圖的無圈邊色數(shù)為4的一個(gè)充分條件.

在給出本文主要結(jié)論及其證明之前,先介紹外平面圖的結(jié)構(gòu)性質(zhì).

引理1[14]每個(gè)2-連通的外平面圖G必含以下子結(jié)構(gòu)之一(如圖2所示):

1)2個(gè)相鄰的2-點(diǎn)u和v;

2)一個(gè)3-圈uvwu使得d(u)=2,d(w)=3;

3)2個(gè)3-圈uvxu和u′v′xu′相交于一點(diǎn)x,使得d(u)=d(u′)=2,d(x)=4.

令M和(A1)～(A7)是如圖3所示的子圖形.

定理1設(shè)G是外平面圖且Δ=4.若G不含子圖與M同構(gòu),則a′(G)=4.

證明 假設(shè)G是一個(gè)最大度為4的外平面圖,且不含與M同構(gòu)的子圖.只需證明G有一個(gè)無圈4-邊染色c.若|V(G)|≤5,則結(jié)論顯然成立.下設(shè)|V(G)|≥6.設(shè)G是邊數(shù)最少的一個(gè)反例.將G嵌入在平面上.由文獻(xiàn)[12],可設(shè)G是2-連通的.再由引理1知,G必含子結(jié)構(gòu)(1)～(3)(如圖2所示).用C={1,2,3,4}表示一個(gè)色集.

d(u)=d(v)=2 d(u)=2,d(w)=3 d(u)=d(u′)=2,d(x)=4(1) (2) (3) 圖2 引理1中的子結(jié)構(gòu)

1)G含有2個(gè)相鄰的2-點(diǎn)u和v.

設(shè)u′≠v是u的另一個(gè)鄰點(diǎn),v′≠u是v的另一個(gè)鄰點(diǎn).令H=G-v+uv′,則H是一個(gè)外平面圖且Δ(H)=Δ=4,|E(H)|<|E(G)|.若H不含子圖與M同構(gòu),則a′(H)=4.由G的極小性知,H有一個(gè)無圈4-邊染色c.此時(shí),用c(uv′)染vv′,并用C{c(u′u),c(uv′)}中的某色染uv.否則,H中含子圖與M同構(gòu).這也意味著G中含子圖與(A1)同構(gòu).

令H′=G-uv,則H′是一個(gè)外平面圖且Δ(H)=Δ=4,|E(H)|<|E(G)|.更進(jìn)一步,H′中不含子圖與M同構(gòu).由G的極小性知,H′有一個(gè)無圈4-邊染色c.若c(uu′)≠c(vv′),則用C{c(uu′),c(vv′)}中的某色染uv.否則,c(uu′)=c(vv′).因d(v′)=3,故CC(v′)≠?.此時(shí),用CC(v′)中的某色染uv.

2)G含有一個(gè)3-圈uvwu,使得d(u)=2,d(w)=3.

設(shè)x≠u,v是w的第3個(gè)鄰點(diǎn).

①假設(shè)d(v)=3或d(x)=2.

令H=G-uw,則H是一個(gè)外平面圖且Δ(H)=Δ=4,|E(H)|<|E(G)|.更進(jìn)一步,H不含子圖與M同構(gòu).由G的極小性知,H有一個(gè)無圈4-邊染色c.若c(uv)≠c(wx),則用C{c(uv),c(wx)}中的某色染uw.否則,c(uv)=c(wx).若d(v)=3,則用CC(v)中的某色染uw.下設(shè)d(x)=2.因|C(w)∪C(x)|≤3,故C(C(w)∪C(x))≠?.此時(shí),用C(C(w)∪C(x))中的某色染uw.

②假設(shè)d(v)=4且d(x)≥3.

i)假設(shè)vx?E(G).

令H=G-{u,w}+vx,則H是一個(gè)外平面圖且dH(x)=d(x)≥3,dH(v)=3.若H不含子圖與M同構(gòu),則a′(H)=4.由G的極小性知,H有一個(gè)無圈4-邊染色c.不妨設(shè)C(v)={1,2,3},并有c(vx)=1.此時(shí),用1染{uv,wx},4染vw,再用2染uw.易驗(yàn)證G沒有雙色圈.否則,H中含子圖與M同構(gòu).這也意味著G中含子圖與(A2)同構(gòu).令H′=G-{u,v,w,y},則H′是一個(gè)外平面圖且Δ(H′)=Δ=4,|E(H′)|<|E(G)|.更進(jìn)一步,H′不含子圖與M同構(gòu).由G的極小性知,H′有一個(gè)無圈4-邊染色c.不妨設(shè)C(x)={1,2,3}并有c(xy1)=2,c(xx1)=3.此時(shí),先用4染{vu,xw},再分別用3,2,1染vy1,vy,vw.繼而,若c(x1y1)=1,則用4染yy1,再用3染uw.否則,用1染yy1,再用2染uw.

ii)假設(shè)vx∈E(G).

設(shè)y≠u,w,x是v的第4個(gè)鄰點(diǎn).

假設(shè)xy∈E(G).因G是2-連通的且不含子圖與M同構(gòu),故d(x)=4,d(y)=3.設(shè)x1≠y,v,w是x的第4個(gè)鄰點(diǎn),y1≠v,x是y的第3個(gè)鄰點(diǎn).令H=G-uw,則H是一個(gè)外平面圖且Δ(H)=Δ=4,|E(H)|<|E(G)|.更進(jìn)一步,H不含子圖與M同構(gòu).由G的極小性知,H有一個(gè)無圈4-邊染色c.若c(uv)≠c(wx),則用C(C(w)∪{c(uv)})中的某色染uw.否則,不妨設(shè)c(uv)=c(wx)=1.若對(duì)某個(gè)1∈CC(w),H中不含(1,a)(u,w)-路,則用a染uv.否則,下設(shè)對(duì)任意的i∈CC(w),H中含(1,i)(u,w)-路.因此,可再設(shè)c(xy)=c(vw)=2,c(xx1)=c(vy)=4,c(vx)=3及c(yy1)=1.此時(shí),分別用1,3,2,4 染或改染{uw,vx},{wx,vy},uv及vw.可以發(fā)現(xiàn)G中沒有雙色圈.

假設(shè)xy?E(G).令H=G-{u,v,w}+xy,則2≤dH(x)=d(x)-1≤3.若H不含子圖與M同構(gòu),則a′(H)=4.由文獻(xiàn) [12]中的結(jié)論及G的極小性知,H有一個(gè)無圈4-邊染色c.不妨設(shè)c(yx)=1,2?C(x).此時(shí),分別用1,2,3,4 染{vy,xw},{vx,uw},vw及uv.可以驗(yàn)證G中沒有雙色圈.否則,H中含子圖與M同構(gòu).這也意味著G中含子圖與(A3)～(A6)中的某個(gè)同構(gòu).

a)假設(shè)G中含子圖與(A3)或(A4)同構(gòu).令H′=G-{u,v,w,x},則H′是一個(gè)外平面圖且Δ(H′)=Δ=4,|E(H′)|<|E(G)|.更進(jìn)一步,H′不含子圖與M同構(gòu).由G的極小性知,H′有一個(gè)無圈4-邊染色c.先設(shè)G中含子圖與(A3)同構(gòu).不妨設(shè)c(yz)=1,c(yz1)=2及c(yy1)=3.此時(shí),分別用1,2,4,3染{uw,vx},{uv,xz},{wx,vy}及wv.再設(shè)G中含子圖與(A4)同構(gòu).不妨設(shè)c(yz)=1,c(zy1)=2及c(zz1)=3.此時(shí),用1,4,2,3染{uw,vx},{uv,xz},{wx,vy}及wv.

b)假設(shè)G中含子圖與(A5)同構(gòu).令H′=G-{u,v,w,y},則H′是一個(gè)外平面圖且Δ(H′)=Δ=4,|E(H′)|<|E(G)|.更進(jìn)一步,H′不含子圖與M同構(gòu).由G的極小性知,H′有一個(gè)無圈4-邊染色c.不妨設(shè)c(xy1)=1,c(y1z)=2及c(y1z1)=3.此時(shí),先用2染{yv,xw}.繼而,若c(xz)=3,則分別用4,1,3染{yy1,xv,uw},vw和uv.否則,c(xz)=4,分別用4,3,1染 {yy1,uv},{xv,uw}和vw.

c)假設(shè)G中含子圖與(A6)同構(gòu).令H′=G-{u,v,w,x,z},則H′是一個(gè)外平面圖且Δ(H′)=Δ=4,|E(H′)|<|E(G)|.更進(jìn)一步,H′不含子圖與M同構(gòu).由G的極小性知,H′有一個(gè)無圈4-邊染色c.不妨設(shè)C(y)={1,2,3},c(yz1)=3及c(yy1)=2.先分別用1,2,3,4 染{xv,wu},xz1,xz和{xw,yv}.繼而,若c(y1z1)=1,則分別用4,2,3染zz1,vw和uv.否則,c(y1z1)=4,分別用1,3,2染zz1,vw,uv.

3)G含有2個(gè)3-圈uvxu和u′v′xu′相交于一點(diǎn)x,使得d(u)=d(u′)=2,d(x)=4.

分2種子情形進(jìn)行討論:

①假設(shè)min{d(v),d(v′)}=3.

不妨設(shè)d(v)=3,并設(shè)y≠u,x是v的第3個(gè)鄰點(diǎn).令H=G-uv,則H是一個(gè)外平面圖且Δ(H)=Δ=4,|E(H)|<|E(G)|.更進(jìn)一步,H不含子圖與M同構(gòu).由G的極小性知,H有一個(gè)無圈4-邊染色c.若c(vy)≠c(ux),則用C{c(vy),c(ux)}中的某色染uv.否則,c(vy)=c(ux)=1.若c(u′v′)=1,則用c(xv′)染uv.否則,用c(xu′)染uv.

②假設(shè)d(v)=d(v′)=4.

假設(shè)vv′∈E(G).設(shè)z≠v,x,u′是v′的第4個(gè)鄰點(diǎn),y≠u,x,v′是v的第4個(gè)鄰點(diǎn).若y=z,則易證結(jié)論成立.因此,下設(shè)y≠z.此時(shí),vz,yv′?E(G).令H=G-{u,x,u′,v}+v′y.此時(shí),dH(v′)=2.假設(shè)H不含子圖與M同構(gòu).由G的極小性知,H有一個(gè)無圈4-邊染色c.不妨設(shè)c(yv′)=1,c(v′z)=2.分別用1,4,3,2染{vy,u′v′,ux},{uv,xv′},{vv′,xu′}和xv.易見G中沒有雙色圈.

否則,下設(shè)H中含子圖與M同構(gòu).這意味著G中含子圖與(A7)同構(gòu).令H′=G-{u,x,u′,v,v′},則H′是一個(gè)外平面圖且Δ(H′)=Δ=4,|E(H′)|<|E(G)|.更進(jìn)一步,H′不含子圖與M同構(gòu).由G的極小性知,H′有一個(gè)無圈4-邊染色c.不妨設(shè)C(y)={1,2,3},并有c(yz)=1,yz1=2.此時(shí),分別用4,1,2,3染{ux,u′v′,vy},{xu′,vv′},{v′z,xv}和{uv,xv′}.

假設(shè)vv′?E(G).令H=G-{u,u′}+vv′.此時(shí),dH(v′)=dH(v)=4,dH(x)=2,且H中不可能含子圖與M同構(gòu)(不然,會(huì)與外平面圖的定義矛盾).由G的極小性知,H有一個(gè)無圈4-邊染色c.不妨設(shè)c(vv′)=1,c(vx)=2及c(xv′)=3.分別用2,1,3,4染vx,{xv′,uv},{ux,u′v′}和xu′.

綜上所述,均能得到G的一個(gè)無圈4-邊染色,矛盾.定理1證畢.

由定理1立即得到下面推論:

推論1設(shè)G是Δ=4且不含相鄰三角形的外平面圖,則a′(G)=4.

參考文獻(xiàn)：

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

[2]Alon N,McDiarmid C,Reed B.Acyclic coloring of graphs[J].Random Structures Alrorithms,1991,2(3):277-288.

[3]Esperet L,Parreau A.Acyclic edge-coloring using entropy compression[J].European J Combin,2013,34(6):1019-1027.

[5]Alon N,Sudakov B,Zaks A.Acyclic edge colorings of graphs[J].J Graph Theory,2001,37(3):157-167.

[6]Alon N,Zaks A.Algorithmic aspects of acyclic edge coloring[J].Algorithmica,2002,32(4):611-614.

[7]Basavaraju M,Chandran L S.A note on acyclic edge coloring of complete bipartite graphs[J].Discrete Math,2009,309(13):4646-4648.

[8]Basavaraju M,Chandran L S.Acyclic edge coloring of subcubic graphs[J].Discrete Math,2008,308(24):6650-6653.

[9]Basavaraju M,Chandran L S.Acyclic edge coloring of graphs with maximum degree 4[J].J Graph Theory,2009,61(3):192-209.

[10]Basavaraju M,Chandran L S,Cohen N,et al.Acyclic edge-coloring of planar graphs[J].SIAM J Discrete Math,2011,25(2):463-478.

[11]Wang Weifan,Shu Qiaojun,Wang Yiqiao.A new upper bound on the acyclic chromatic indices of planar graphs[J].European J Combin,2013,34(2):338-354.

[12]Muthu R,Narayanan N,Subramanian C R.Acyclic edge coloring of outerplanar graphs[C]//Kao Mingyang,Li Xiangyang.Lecture Notes in Computer Science 4508:Aspects in information and management.Berlin:Springer,2007:144-152.

[13]Hou Jianfeng,Wu Jianliang,Liu Guizhen,et al.Acyclic edge chromatic number of outerplanar graphs[J].J Graph Theory,2010,64(1):22-36.

[14]王維凡,張克民.Δ-匹配與邊面全染色[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),1999,22(2):236-242.