不含特殊短圈平面圖的無圈邊染色*

鄭麗娜

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華 321004)

0 引言

本文僅考慮有限簡單圖．給定一個(gè)圖G，用V(G)，E(G)，Δ(G)，δ(G)分別表示它的頂點(diǎn)集、邊集、最大度、最小度．若uv∈E(G)，則稱點(diǎn)u為點(diǎn)v的鄰點(diǎn)，并用N(v)表示點(diǎn)v的鄰點(diǎn)集合．點(diǎn) v的度d(v)=|N(v)|;k-點(diǎn)(k+-點(diǎn)，k--點(diǎn))表示度是k(至少為k，至多為k)的頂點(diǎn)．若能將圖G畫在平面上，使得它的邊僅在端點(diǎn)處相交，則稱G是可平面圖．圖的這種平面圖上的畫法稱為圖的平面嵌入，或稱為平面圖．

圖G的正常k-邊染色是指映射c：E(G)→{1，2，…，k}使得相鄰的邊染不同的顏色;若G有一個(gè)k-邊染色，則稱圖G是k-邊可染的;無圈k-邊染色是指圖G的一個(gè)正常的k-邊染色，使其不產(chǎn)生雙色圈;無圈邊色數(shù)a'(G)是指使得圖G有一個(gè)無圈k-邊染色的最小整數(shù)k．

無圈邊染色的概念最早是由 Fiamcˇík［1］提出的．Alon 等［2］證明了：對(duì)任何圖 G 有 a'(G)≤64Δ(G);Molloy和 Reed［3］將這個(gè)界改進(jìn)到 a'(G)≤16Δ(G);2005 年，Muthu等［4］證明了當(dāng) g(G)≥220 時(shí)，a'(G)≤4．52Δ(G)．2001 年，Alon 等［5］提出了如下著名的無圈邊染色猜想：

猜想1 對(duì)任意圖G，有a'(G)≤Δ(G)+2．

猜想1至今還未得到證實(shí)，僅知道一些特殊圖類滿足猜想1．Alon等［6］證明了確定任意圖G的無圈邊色數(shù)是一個(gè)NP-問題．Cohen等［7］還提出了如下猜想：

猜想2 設(shè)G是一個(gè)平面圖，則存在一個(gè)整數(shù)Δ0，使得當(dāng)Δ(G)≥Δ0時(shí)，就有a'(G)=Δ(G)．

對(duì)于不含特殊短圈的平面圖，文獻(xiàn)［8］證明了：若G不含4到8-圈，則a'(G)≤Δ(G)+2;文獻(xiàn)［9］證明了：若G不含4-圈，5-圈或G不含4-圈，6-圈，則a'(G)≤Δ(G)+2;文獻(xiàn)［10］證明了：若G不含4到11-圈且Δ(G)≥10或G不含4到9-圈且Δ(G)≥11，則a'(G)≤Δ(G)+1．

本文主要研究了不含特殊短圈平面圖的無圈邊染色問題，得到了以下結(jié)果：

定理1 設(shè)G是一個(gè)平面圖，如果G不含4到8-圈，那么a'(G)≤Δ(G)+1．

1 結(jié)構(gòu)引理

本節(jié)討論的全部是平面圖，且假設(shè)它們已經(jīng)嵌入到平面上．設(shè)圖G是平面圖，通常用F(G)表示面集;對(duì)于f∈F，用d(f)表示面 f的度數(shù);若一個(gè)k-面沿著某個(gè)方向的點(diǎn)依次為u1，u2，…，uk，則稱這個(gè)面為(d(u1)，d(u2)，…，d(uk))-面;k-面(k+-面，k--面)表示度是 k(至少為 k，至多為 k)的面;(i，j，k+)-面表示i-點(diǎn)，j-點(diǎn)和 k+-點(diǎn)相連的3-面，其中i≤j≤k;對(duì)G的一個(gè)邊染色c和頂點(diǎn)v∈V(G)，設(shè) C(v)={c(uv)|u∈N(v)}．

設(shè)圖G是滿足定理1條件的一個(gè)邊數(shù)極小反例，那么G是2-連通的．否則，設(shè)v是G的一個(gè)割點(diǎn)，G1，G2，…，Gt(t≥2)是 Gv的連通分支．由 G 的極小性知，對(duì)任意1≤i≤t，G'i=Gi∪{v}都有無圈 k-邊染色ci．若點(diǎn)v相關(guān)聯(lián)的邊出現(xiàn)相同顏色，則通過每個(gè)ci進(jìn)行色置換，使得點(diǎn)v相關(guān)聯(lián)的邊染不同色，從而可得G的一個(gè)無圈k-邊染色，與G的極小性矛盾．

設(shè) k=Δ(G)+1，為方便討論，令顏色集 C={1，2，…，k}．此外，簡記 Δ =Δ(G)．

首先給出一些定理1證明中需要用到的引理．

引理1 若d(v)=2，則v不與3--點(diǎn)相鄰．

證明 假設(shè)v與一個(gè)3--點(diǎn)u相鄰．設(shè)w≠u是v的另一鄰點(diǎn)，G'=G-uv．由G的極小性知，G'有無圈 k-邊染色 c，染色集 C={1，2，…，k}，不妨設(shè) c(vw)=1．

1)若1?C(u)，則用a0∈C(C(u)∪{1})染 uv．因|C(C(u)∪{1})|≥k-3≥1，故這樣的顏色a0存在，且染色c仍是無圈的．

2)1∈C(u)．若存在 a1∈C(C(u)∪C(w))，則用 a1染 uv．否則，設(shè) d(u)=3，u1≠v，u2≠v是 u 的另外 2 個(gè)鄰點(diǎn)，c(uu1)=1，c(uu2)=2，A1=C{1，2}．若存在 b0∈A1，使得 G'中不含(1，b0)(u1，w)-雙色路，則用 b0染 uv．否則，假設(shè)對(duì)于任意 i∈A1，G'中均有(1，i)(u1，w)-雙色路，則 A1?C(w)∩C(u1)．又因d(w)≤Δ，d(u1)≤Δ，故C(w)=C(u1)=C{2}，因此可用2改染vw．與前面討論類似，可設(shè)對(duì)于任意i∈A1，G'中均有(2，i)(u2，w)-雙色路且 C(u2)=C{1}．此時(shí)交換 uu1和 uu2所染的色，再用 3 染 uv，從而可得G的一個(gè)無圈 k-邊染色，與G的極小性矛盾．所以，v不與3--點(diǎn)相鄰．引理1證畢．

引理2 若d(v)=d≥4，則v至多與d-2個(gè)2-點(diǎn)相鄰．

證明 假設(shè)存在一個(gè) d-點(diǎn)v與d-1 個(gè)2-點(diǎn)相鄰．設(shè)N(v)={u1，u2，…，ud}，d(ui)=2，N(ui)={v，wi}，i=1，2，…，d-1，G'=G-u1v．由 G 的極小性知，G'有無圈 k-邊染色 c，染色集 C={1，2，…，k}，不妨設(shè) c(uiv)=i，i=2，3，…，d．

1)若 c(u1w1)?{2，3，…，d}，則用 a2∈C({2，3，…，d}∪{c(u1w1)})染 u1v．因|C({2，3，…，d}∪{c(u1w1)})|≥k-d≥1，故這樣的顏色a2存在，且染色c仍是無圈的．

2)若 c(u1w1)∈{2，3，…，d-1}，不妨設(shè) c(u1w1)=2，則用 a3∈C({2，3，…，d}∪{c(u2w2)})染u1v．因|C({2，3，…，d}∪{c(u2w2)})|≥k-d≥1，故這樣的顏色 a3存在，且染色 c仍是無圈的．

3)c(u1w1)=d．若存在 a4∈{1，d+1，d+2，…，k}C(w1)，則用 a4染 u1v．否則，{1，d+1，d+2，…，k}?C(w1)．又因?yàn)?d(w1)≤Δ 且 d∈C(w1)，所以至少存在1個(gè)顏色 j∈{2，3，…，d-1}C(w1)．此時(shí)，用 j改染u1w1，用a5∈C({2，3，…，d}∪{c(ujwj)})染u1v，可得G 的一個(gè)無圈k-邊染色，與G 的極小性矛盾．所以，v至多與d-2個(gè)2-點(diǎn)相鄰．引理2證畢．

引理3 在3-面的邊界上沒有2-點(diǎn)與4-點(diǎn)相鄰．

證明 假設(shè)一個(gè)2-點(diǎn)u與一個(gè)4-點(diǎn)v相鄰在一個(gè)3-面uvw的邊界上，G'=G-uv．由G的極小性知，G'有無圈 k-邊染色 c，染色集 C={1，2，…，k}，不妨設(shè) c(uw)=1，c(vw)=2．

1)若1?C(v)，則用 a6∈C(C(v)∪{1})染 uv．因|C(C(v)∪{1})|≥k-4≥1，故這樣的顏色 a6存在，且染色c仍是無圈的．

2)1∈C(v)．設(shè) v1，v3是 v的另外2 個(gè)鄰點(diǎn)，c(vv1)=1，c(vv3)=3，A3=C{1，2，3}．若存在 b1∈A3，使得 G'中不含(1，b1)(v1，w)-雙色路，則用 b1染 uv．否則，假設(shè)對(duì)于任意 j∈A3，G'中均有(1，j)(v1，w)-雙色路，則 A3?C(w)∩C(v1)．又因 d(w)≤Δ，故 C(w)=C{3}．進(jìn)一步，可假設(shè)對(duì)于任意 j∈A3，G'中均有(3，j)(v3，w)-雙色路，則 A3?C(w)∩C(v3)．

只需考慮 d(v1)=d(v3)=Δ．顯然有|{1，2，3}∩C(vi)|=2，i=1，3．此時(shí)，先抹去 uw 的色．

①若2∈C(v1)∩C(v3)，則交換vv1與 vv3所染的色，用3染uw，再用4染uv．

②若2?C(vi)，i∈{1，3}，即 3∈c(vv1)，1∈c(vv3)，則 C(v1)=C(v3)=C{2}．若 w 到 v1無(2，4)-雙色路，則分別用 2，1 改染 vv1，vw，用3 染 uw，再用4 染uv．若 w 到v1有(2，4)-雙色路，則分別用2，1改染vv3，vw，用3染uw，再用4染uv．由雙色路的唯一性知，w到v3無(2，4)-雙色路．

③若2∈C(v1)，且2?C(v3)，則分別用 3，2，1 改染 vv1，vv3，vw，用3 染 uw，再用 4 染 uv．

綜上，可得G的一個(gè)無圈k-邊染色，與G的極小性矛盾．所以，在3-面的邊界上沒有2-點(diǎn)與4-點(diǎn)相鄰．引理3證畢．

引理4 若d(v)=4且v相鄰2個(gè)2-點(diǎn)，則v不會(huì)關(guān)聯(lián)3-面．

證明 假設(shè)v關(guān)聯(lián)一個(gè)3-面uvw．設(shè)x，y是與 v相鄰的2個(gè)2-點(diǎn)，x1，y1分別是2-點(diǎn) x，y的另一鄰點(diǎn)，G'=G-vx．由 G 極小性知，G'有無圈 k-邊染色 c，染色集 C={1，2，…，k}．

1)若 c(xx1)?C(v)，則用 a7∈C(C(v)∪{c(xx1)})染 vx．因|C(C(v)∪{c(xx1)})|≥k-4≥1，故這樣的顏色a7存在，且染色c仍是無圈的．

2)c(xx1)∈C(v)，不妨設(shè) c(vy)=1，c(vw)=2，c(uv)=3，A4=C{1，2，3}．考慮到 u，w 的對(duì)稱性，故只需考慮以下2種情形：

①若 c(xx1)=1，則用 a8∈C(C(v)∪{c(yy1)})染 vx．因|C(C(v)∪{c(yy1)})|≥k-4≥1，故這樣的顏色a8存在，且染色c仍是無圈的．

②c(xx1)=2．若存在a9∈C(C(v)∪C(w))，則用a9染vx．否則，可斷言對(duì)于A4中的任一個(gè)顏色i都有x1到w的(2，i)-雙色路，故A4?C(w)∩C(x1)．進(jìn)一步，若1?C(x1)，則用1改染 xx1，轉(zhuǎn)至情形①．若1∈C(x1)，C(x1)=C{3}，則可假設(shè)對(duì)于A4中的任一個(gè)顏色i都有x1到u的(3，i)-雙色路，故A4?C(u)∩C(x1)．考慮uw邊的染色情況，可分以下2種情況加以討論：

i)當(dāng)c(uw)=1時(shí)，C(w)=C{3}，C(u)=C{2}，可斷言 x1到 w 和 x1到 u無(2，1)-雙色路．此時(shí)，可用 C({1，2，3}∪{c(yy1)})中的某一色改染 vy，再用1染 vx．

ii)當(dāng) c(uw)∈A4時(shí)，C(w)=C{1}，C(u)=C{1}，可斷言 x1到 w 和 x1到 u 無(2，1)-雙色路．此時(shí)，可用C({1，2，3}∪{c(yy1)})中的某一色改染vy，再用1染vx，從而可得G的一個(gè)無圈k-邊染色，與G的極小性矛盾．所以，v不會(huì)關(guān)聯(lián)3-面．引理4證畢．

引理5 在3-面的邊界上沒有2個(gè)3-點(diǎn)相鄰．

證明 假設(shè)一個(gè)3-點(diǎn)u與一個(gè)3-點(diǎn)v相鄰在一個(gè)3-面uvw的邊界上．設(shè)u1≠w，v1≠w分別是u，v的另一鄰點(diǎn)，G'=G-uv．由 G 的極小性知，G'有無圈 k-邊染色 c，染色集 C={1，2，…，k}，設(shè) c(uu1)=1，c(uw)=2．

1)|C(u)∩C(v)|=0．不妨設(shè) c(vw)=3，c(vv1)=4．

①若 Δ≥4，則用a10∈C(C(u)∪C(v))染 uv．因 |C(C(u)∪C(v))|≥k-4≥1，故這樣的顏色a10存在，且染色c仍是無圈的．

②下設(shè) Δ =3，w1是 w 的另一鄰點(diǎn)，染色集 C={1，2，3，4}．若3?C(u1)，則用3 改染 uu1，再用1 染uv;若2?C(v1)，則用2改染vv1，再用4 染uv．設(shè)3∈C(u1)，2∈C(v1)．考慮到c(ww1)的對(duì)稱性，不妨設(shè)c(ww1)=1．若 u1到 w1無(1，4)-雙色路，則用4 改染 uw，再用 2 染 uv．否則，設(shè) u1到 w1有(1，4)-雙色路，且 4∈C(u1)，4∈C(w1)，C(u1)=C{2}．此時(shí)，用 4 改染 uw，2 改染 uu1，再用1 染 uv．

2)|C(u)∩C(v)|=1．

①c(uu1)=c(vw)或c(vv1)=c(uw)．由于這2種情況的證明過程相同，故不妨設(shè)c(uu1)=c(vw)=1，c(vv1)=3，A5=C{1，2，3}．可斷言對(duì)于 A5中的任一個(gè)顏色 i都有 u1到 w 的(1，i)-雙色路，故 A5?C(w)∩C(u1)，且 C(w)=C{3}．若 u1到 v1無(1，3)-雙色路，則用3 改染 uw，再用2 染 uv．否則，設(shè) u1到 v1有(1，3)-雙色路，且3∈C(u1)，C(u1)=C{2}，1∈C(v1)．又若 A5C(v1)≠?，不妨設(shè) 4?C(v1)，則用4改染vv1，再用3染uv．所以設(shè)A5?C(v1)=C{2}．此時(shí)，用2改染vv1，再用3染uv．

②c(uu1)=c(vv1)．不妨設(shè) c(uu1)=c(vv1)=1，c(vw)=3，A5=C{1，2，3}．可斷言對(duì)于 A5中的任一個(gè)顏色i都有u1到v1的(1，i)-雙色路，故A5?C(u1)∩C(v1)．若3?C(u1)，則用3改染uu1，轉(zhuǎn)化至情形①．因此，3∈C(u1)，C(u1)=C{2}．若2?C(v1)，則用 2 改染 vv1，轉(zhuǎn)化至情形①．因此，2∈C(v1)，C(v1)=C{3}．又若 A5C(w)≠?，不妨設(shè)4?C(w)，則用4改染 vw，再用3染 uv．所以下設(shè) A5?C(w)=C{1}．此時(shí)，用3改染vv1，用1改染vw，再用4染 uv．

3)|C(u)∩C(v)|=2．若 c(uu1)=c(uw)，c(vv1)=c(vw)，不妨設(shè) c(uu1)=c(uw)=1，c(vv1)=c(vw)=2，則用a11∈CC(w)染uv，從而可得G的一個(gè)無圈k-邊染色，與G的極小性矛盾．所以，在3-面的邊界上沒有2個(gè)3-點(diǎn)相鄰．引理5證畢．

引理6 若d(v)=5且v相鄰3個(gè)2-點(diǎn)，則v不與2-點(diǎn)關(guān)聯(lián)在一個(gè)3-面中．

證明 假設(shè)v與一個(gè)2-點(diǎn)u關(guān)聯(lián)在一個(gè)3-面uvw中．設(shè)x，y是與v相鄰的其他的2個(gè)2-點(diǎn)，z是v的另一個(gè)鄰點(diǎn)，x1，y1分別是2-點(diǎn)x，y的另一鄰點(diǎn)，G'=G-uv．由G 極小性知，G'有無圈k-邊染色c，染色集C={1，2，…，k}．若 c(uw)?C(v)，則用 a12∈C(C(v)∪{c(uw)})染 uv．否則，c(uw)∈C(v)，不妨設(shè)c(vx)=1，c(vy)=2，c(vz)=3，c(vw)=4．

1)若 c(uw)=1，則用 a13∈C(C(v)∪{c(xx1)})染 uv．2)若 c(uw)=2，則用 a14∈C(C(v)∪{c(yy1)})染 uv．3)c(uw)=3．因 d(w)≤Δ，故可記 C(w)中未出現(xiàn)的色為 c0，c0∈C{3，4}．當(dāng) c0=1時(shí)，用1改染uw，轉(zhuǎn)至情形1);當(dāng)c0=2時(shí)，用2改染uw，轉(zhuǎn)至情形2);當(dāng)c0∈CC(v)時(shí)，直接將c0染uv，從而可得G的一個(gè)無圈k-邊染色，與G的極小性矛盾．所以，v不與2-點(diǎn)關(guān)聯(lián)在一個(gè)3-面中．引理6證畢．

2 定理1的證明

設(shè)圖G是滿足定理1條件的一個(gè)邊數(shù)極小反例．以下將運(yùn)用Discharging方法導(dǎo)出完成定理1證明所需要的矛盾．

對(duì)任意 x∈V(G)∪F(G)，構(gòu)造一個(gè)權(quán)函數(shù) ω(x)．其中：當(dāng) v∈V(G)時(shí)，ω(v)=2d(v)-6;當(dāng) f∈F(G)時(shí)，ω(f)=d(f)-6．通過權(quán)轉(zhuǎn)移，得到一個(gè)新的權(quán)函數(shù)ω'(x)，使得總的權(quán)和不變．但對(duì)任意的x∈V(G)∪F(G)，有ω'(x)≥0．因此得到-12≥0，即得到了證明定理1所需要的矛盾．．

設(shè)v∈V(G)，n2(v)表示與點(diǎn)v相鄰的2-點(diǎn)個(gè)數(shù)，f3(v)表示點(diǎn)v關(guān)聯(lián)的3-面?zhèn)€數(shù)．

權(quán)轉(zhuǎn)移規(guī)則如下：

首先驗(yàn)證 ω'(v)≥0，v∈V(G)．

情形1 v為2-點(diǎn)．由引理1和(R1)知，ω'(v)=2×2-6+1×2=0．

情形2 v為3-點(diǎn)．由權(quán)轉(zhuǎn)移規(guī)則知v既不轉(zhuǎn)出權(quán)也不接受權(quán)，故ω'(v)=2×3-6=0．

其次驗(yàn)證 ω'(f)≥0，f∈F(G)．

［1］Fiamcˇík I．The acyclic chromatic class of a graph［J］．Math Slovaca，1978，28(3)：139-145．

［2］Alon N，McDiarmid C，Reed B．Acyclic coloring of graphs［J］．Random Structures Algorithms，1991，2(3)：277-288．

［3］Molloy M，Reed B．Further algorithmic aspects of Lovász local lemma［C］//Proceedings of the 30th Annual ACM Symposium on Theory of Computing held in Dallas．Dallas：ACM，1998：524-529．

［4］Muthu R，Narayanan N，Subramanian C R．Improved bounds on acyclic edge coloring［J］．Discrete Math，2007，307(23)：3063-3069．

［5］Alon N，Sudakov B，Zaks A．Acyclic edge colorings of graphs［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］Cohen N，Havet F，Müller T．Acyclic edge-colouring of planar graphs，Extended abstract［J］．Eletronic Notes in Discrete Math，2009，34(5)：417-421．

［8］Sun Xiangyong，Wu Jianliang．Acyclic edge colorings of planar graphs without short cycles［C］//Proceedings of the 7th International Symposium on Operations Research and Its Applications held in Lijiang．Lijiang：APORC＆CAS，2008：325-329．

［9］Hou Jianfeng，Liu Guizhen，Wu Jianliang．Acyclic edge coloring of planar graphs without small cycles［J］．Graphs andCombinatorics，2011：10．1007/s00373-011-1043-0．

［10］Gao Yunshu，Yu Dongxiao．Acyclic edge coloring of planar graphs without cycles of specific lengths［J］．Appl Math Comput，2011，37(2)：533-540．