平面圖的無(wú)圈邊染色

王藝橋，舒巧君

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

0 引言

本文考慮有限簡(jiǎn)單圖.給定一個(gè)圖G，用V（G）和E（G）分別表示它的頂點(diǎn)集和邊集.令Ck＝u1u2…uku1是G中長(zhǎng)為k的圈.若兩個(gè)圈至少有一條公共邊，就稱這兩個(gè)圈為相鄰的.設(shè)Δ和δ分別表示一個(gè)圖G的最大度和最小度.

圖G的正常邊k染色是指映射c：E（G）→｛1，2，…，k｝，使得相鄰的邊染不同的顏色.G 的邊色數(shù)χ′（G）是指使得G是邊k可染的最小整數(shù)k.無(wú)圈邊k染色是指G的一個(gè)正常的邊k染色，使得不產(chǎn)生雙色圈.無(wú)圈邊色數(shù)a′（G）是指使得G是無(wú)圈邊k染色的最小整數(shù)k.由著名的Vizing's定理知，Δ≤χ′（G）≤Δ＋1.因此，顯然有a′（G）≥χ′（G）≥Δ.Fiamˇcik［1］，Alon等［2］先 后 分 別 提 出 了 著 名 的 無(wú) 圈邊色數(shù)猜想.

猜想1 對(duì)任何圖G，a′（G）≤Δ＋2.

1991年，Alon等［3］應(yīng)用概率方法證明了對(duì)任何圖G，有a′（G）≤64Δ.當(dāng)前最好的上界a′（G）≤4Δ－4，由Esperet等［4］得到.一些特殊圖的無(wú)圈邊染色已被廣泛研究，如最大度為3的圖［5］，為4的圖［6－7］.對(duì) 于 平 面 圖 G，Basavaraju 等［8］證 明 了a′（G）≤Δ＋12.Wang等［9］將12降到7，且證明了當(dāng)G符合以下幾個(gè)條件之一時(shí)，猜想1成立：i）不含3圈［10］；ii）不含4圈［11］；iii）不含5圈［12］；iv）不含3圈和4圈相鄰［13］.相關(guān)結(jié)果參見(jiàn)［14］.

本文旨在研究不含3圈和5圈相鄰的平面圖的無(wú)圈邊色數(shù).將證明此類圖也是滿足猜想1的，這在一定程度上改進(jìn)了文獻(xiàn)［11－12］中的結(jié)果和擴(kuò)充了［13］中的結(jié)果.

1 結(jié)構(gòu)分析

給定一個(gè)圖G，令dG（v）（或d（v））表示頂點(diǎn)v在G中的度.度為k（至少為k，至多為k）的頂點(diǎn)稱為k點(diǎn)（k＋點(diǎn)，k－點(diǎn)）.對(duì)于平面圖H，用F（H）表示其面集合，并用dH（f）（或d（f））表示面f∈F（H）的度.類似地，可定義k面，k＋面以及k－面.對(duì)于f∈F（H），用b（f）表示面f的邊界，若一個(gè)面f沿著某 個(gè) 方 向 的 點(diǎn) 依 次 為 u1，u2，…，un，則 記 為f＝［u1u2…un］.

引理1 設(shè)G為Δ≥5的2連通平面圖，且不含相鄰的3圈和5圈，則G含以下子構(gòu)型A1）～A6）之一（見(jiàn)圖1）：

A1）一條路uvw，使得下列之一成立：

A1.1）d（v）＝2且d（u）≤5；

A1.2）d（u）＝d（v）＝3，且x是v的第三個(gè)鄰點(diǎn)；

A1.3）d（v）＝4且d（u）＝d（w）＝3；

A1.4）d（v）＝3且d（u）＝d（w）＝4；

A1.5）d（v）＝d（x）＝d（y）＝3，d（u）＝4，d（w）＝5，x，y是不同的于v的w 的鄰點(diǎn)；

A1.6）d（v）＝3，d（u）＝4，且uw∈E（G）.

A2）一個(gè)點(diǎn)u使得d2（u）≥1，d2（u）＋d3（u）≥d（u）－3.設(shè)u1，u2，…，ud（u）－1，v 是u 的鄰點(diǎn)，滿足d（u1）≥d（u2）≥…≥d（ud（u）－1）≥d（v）＝2.設(shè) w 是v的不同于u的鄰點(diǎn).若ui（1≤i≤d（u）－1）是一個(gè)2點(diǎn)，則用xi表示不同于u的ui的鄰點(diǎn).于是有下列之一成立：

A2.1）n2（u）＋n3（u）≥d（u）－2；

A2.2）n2（u）＋n3（u）＝d（u）－3，且n3（u）≤1；

A2.3）n2（u）＝d（u）－4，u3u4∈E（G）且對(duì)于i＝3，4，n2（ui）＝d（ui）－4；

A2.4）n2（u）＝d（u）－5，d（u4）＝d（u5）＝3且u3u4∈E（G）.

A3）一個(gè)3圈uvwu，使得d（u）＝d（v）＝d（w）＝4.

A4）一個(gè)5點(diǎn)u相鄰于4個(gè)3點(diǎn)v，x，y，z以及另一個(gè)點(diǎn)w.

A5）一個(gè)5點(diǎn)u相鄰于x，z，w，y，v且有d（v）＝d（z）＝3以及xv，yv，wz∈E（G）.

A6）一個(gè)5點(diǎn)u相鄰于x，v，w，y，z且有d（v）＝d（x）＝d（y）＝3，以及xz，yz，wv∈E（G）.

證 假設(shè)結(jié)論不成立，則G不含子構(gòu)型A1）～A6）中的任何一個(gè).因G是2連通的，故δ≥2.設(shè)G′是移掉G中所有2點(diǎn)后得到的圖，H是G′的一個(gè)連通分支，則H是連通的不含3圈和5圈相鄰的平面圖，且對(duì)于v∈V（H），v在G中的度至少為3.將H嵌入在平面上.

設(shè)u∈V（H），則u∈V（G）.為討論方便，u在G中的度記為d（u），在H 中的度記為dH（u），在H 中的鄰點(diǎn)的集合記為 N′（u）.若dH（u）＝k，令u1，u2，…，uk是u在H 中的鄰點(diǎn)，且按順時(shí)針排列，f1，f2，…，fk是與u關(guān)聯(lián)的面，其中f1＝［…u1uu2…］，f2＝［…u2uu3…］，…，fk－1＝［…uk－1uuk…］，fk＝［…ukuu1…］.對(duì)于k≥1，令n′k（u）（n′k＋（u），n′k－（u））表示在H中與u相鄰的k點(diǎn)（k＋點(diǎn)，k－點(diǎn)）的個(gè)數(shù)，nk（u）（nk＋（u），nk－（u））表示在G 中與u 相鄰的k點(diǎn)（k＋點(diǎn)，k－點(diǎn)）的個(gè)數(shù).與面f∈F（H）相關(guān)聯(lián)的k點(diǎn)（k＋點(diǎn)）的個(gè)數(shù)用nk（f）（nk＋（f））表示.類似地，用mk（u）（mk＋（u））表示在H 中與u 相關(guān)聯(lián)的k面（k＋面）的個(gè)數(shù)，δ（f）表示與f關(guān)聯(lián)的點(diǎn)的最小度.

因?yàn)镚不含A1.1），沒(méi)有5－點(diǎn)會(huì)與2點(diǎn)相鄰，亦即，若u是滿足3≤d（u）≤5的點(diǎn)，則dH（u）＝d（u）.類似地，若d（u）≥6且n2（u）＝0，則dH（u）＝d（u）.又因?yàn)镚 不含A2.1）和 A2.2），每個(gè)6＋點(diǎn)u至多相鄰于d（u）－4個(gè)2點(diǎn)，這也說(shuō)明了：若d（u）≥6且n2（u）≥1，則dH（u）≥4，dH（u）＝d（u）－n2（u）.

類似于文獻(xiàn)［12］中斷言1，2，4，5和文獻(xiàn)［11］中斷言8的證明，有下面斷言1～4成立.

斷言1 Δ（H）≥3，對(duì)u∈V（H），則n′3（u）＝n3（u）且n2（u）＋n3（u）＝d（u）－dH（u）＋n′3（u）.特別地，若dH（u）＝3，則d（u）＝3.

斷言2 若dH（u）＝4且n′3（u）≥1，則d（u）＝4.

斷言3 若H中存在一條路uvwx，使得d（u）＝4，d（v）＝d（x）＝3，dH（w）＝5，則d（w）＝5，n3（w）＝2，或者d（w）≥6，n2（w）＝d（w）－5且n3（w）＝2.

斷言4 設(shè)f＝［uvw］是一個(gè)3面，

a）若δ（f）＝3，則n5＋（f）＝2；

b）若δ（f）＝4，則n4＋（f）＝3且n5＋（f）≥1.

斷言5 若dH（u）＝5且n3（u）≥3，則

a）d（u）＝5；

b）n3（u）＝3，且對(duì)任意的y∈N′（u），x∈N′（y），有d（y）＝3，dH（x）≥5.

證 若d（u）≠5，則n2（u）≥1，n2（u）＋n3（u）＝d（u）－dH（u）＋n3（u）≥d（u）－5＋3≥d（u）－2.因此，G 中就含有 A2.1）.又因?yàn)镚 不含 A4）和 A1.5），所以，b）成立.

斷言6 設(shè)u∈V（H），若d（f1）＝3，則對(duì)于任意的i∈｛2，k｝，d（fi）＝3或d（fi）≥6.且若dH（u）＝k≥4，則

a）若d（f1）＝d（f2）＝3，則d（f3）≥6，d（fk）≥6.

c）若m3（f）≥1，則m6＋（f）≥2.

用權(quán)轉(zhuǎn)移方法來(lái)得出矛盾.首先，由歐拉公式｜V（H）｜－｜E（H）｜＋｜F（H）｜＝2和關(guān)系式

易得到如下等式：

其次，定義權(quán)函數(shù)w：對(duì)于u∈V（H），w（u）＝2dH（u）－6；對(duì)于f∈F（H），w（f）＝dH（f）－6.由（1）可得權(quán)和為－12.接下來(lái)，將定義權(quán)轉(zhuǎn)移規(guī)則R1）～R2），且將按此規(guī)則對(duì)權(quán)進(jìn)行轉(zhuǎn)移.一旦權(quán)轉(zhuǎn)移完成，就會(huì)產(chǎn)生新的權(quán)函數(shù)w′.然而，在權(quán)轉(zhuǎn)移的過(guò)程中，權(quán)和是保持不變的.不過(guò)可以證明對(duì)于所有的x∈V（H）∪F（H）均有w′（x）≥0.這就導(dǎo)出了一個(gè)很明顯的矛盾

因而證明了這樣的反例是不存在的，故引理1成立.

設(shè)u是H 中一個(gè)度為k的點(diǎn).令τ（u→f）表示從點(diǎn)u轉(zhuǎn)到與其相關(guān)聯(lián)面f的權(quán)的量.權(quán)轉(zhuǎn)移規(guī)則定義如下：

R2）設(shè)k≥5.

R2.1）若d（f）＝5且f＝［…xuy…］，則

R2.2）若d（f）＝4且f＝［vuyx］，則

R2.3）若d（f）＝3，則

設(shè)f∈F（H）.由斷言6，對(duì)于任意的u∈V（H），若d（f1）＝3，則對(duì)任意的i∈｛2，k｝，d（fi）＝3或者d（fi）≥6.

假設(shè)d（f）＝3，則w（f）＝d（f）－6＝－3.若δ（f）＝3，則由斷言4知n5＋（f）＝2.由 R2.3），w′（f）＝－3＋2×＝0.若δ（f）≥4，則由 R）和 R），12.3w′（f）≥－3＋3×1＝0.

假設(shè)d（f）＝4且f＝［uvxy］，則w（f）＝d（f）－6＝－2.若δ（f）≥4，則由 R1）和 R2.2）可知，w′（f）≥－2＋4×＝0.因此，下設(shè)δ（f）＝3.因G不含 A1.2）和 A1.3），n3（f）≤2.首先假設(shè)n3（f）＝2，d（v）＝d（y）＝3，d（u）≥5，d（x）≥5.由 R2.2），w′（v）＝－2＋2×1＝0.否則，n3（f）＝1.不妨設(shè)d（v）＝3.因G 不含 A1.4），故max｛d（x），d（u）｝≥5.若d（x）＝4，則由R2.2）或R1），u給f 權(quán)1，x，y至少給f權(quán).因此，w′（f）≥－2＋1＋2×＝0.否則，d（u），d（x）≥5，且由 R2.2）或者 R1），u，x 至少給f權(quán)，y至少給f權(quán).因此，w′（f）≥－2＋2×＋＝0.

假設(shè)d（f）＝5，則w（f）＝d（f）－6＝－1.由R1.1）或 R2.1），b（f）上 的4＋點(diǎn)至少給 f 權(quán).若n＋（f）≥4，則w′（f）≥－1＋4×＝0.否則，因G4不含 A1.2），再由斷言1，不妨設(shè)f＝［uvwxy］且有d（u）＝d（w）＝3，n4＋（f）＝3.因 G 不含 A1.2）和A1.3），故dH（v）≥5.因此，由 R1）和 R2.1），w′（f）≥－1＋1×＋2×＝0.

假設(shè)d（f）≥6，則w′（f）＝w（f）＝d（f）－6≥0.

設(shè)u∈V（H）.由斷言1可知，dH（u）≥3.若dH（u）＝3，則w′（u）＝w（u）＝2dH（u）－6＝0.下設(shè)d（u）≥4.由斷言H

假設(shè)dH（u）≥9，則

假設(shè)dH（u）＝8，則w（u）＝2dH（u）－6＝10且m（u）≤5.若m（u）≤4，則w′（u）≥10－4×－433×1＝0.否則，m3（u）＝5.由斷言6，m6＋（u）≥1，故

假設(shè)dH（u）＝7，則w（u）＝2dH（u）－6＝8且m（u）≤4.若m（u）≤2，則w′（u）≥8－2×3－5×3321＝0.否則，m3（u）≥3.由斷言6，m6＋（u）≥1且w′（u）≥8－4×－（7－1－4）×1＝0.

假設(shè)dH（u）＝6，則w（u）＝2dH（u）－6＝6且m3（u）≤4.若m3（u）＝0，則w′（u）≥6－6×1＝0.否則，1≤m3（u）≤4.由斷言6，m6＋（u）≥2，因此

假設(shè)dH（u）＝4，則w（u）＝2dH（u）－6＝2.若u不與3面關(guān)聯(lián)，則由R）可知w′（u）≥2－4×＝10.否則，下設(shè)1≤m3（u）≤2，d（f1）＝3.由斷言6，m6＋（u）≥2.因此，由R1），w′（u）≥2－1×2＝0.

假設(shè)dH（u）＝5，則w（u）＝2dH（u）－6＝4且m3（u）≤3.只需考慮以下幾種子情形.

情況1 m3（u）＝3.由斷言6，可設(shè)d（f1）＝d（f2）＝d（f4）＝3且d（f3）≥6，d（f5）≥6.因G 不含 A2.4），A5）和 A6），且由斷言5知，f1，f2，f4中至多只有兩個(gè)面的最小度為3.因此，由R2），

情況2 1≤m3（u）≤2.由斷言6，m6＋（u）≥2.所以，w′（u）≥min ｛4－2×－（5－2－2）×1，4－－2×1｝ ＝0.

情況3 m3（u）＝0.因G不含 A4）且由斷言5，n3（u）≤3，則由對(duì)稱性，只需討論以下3種子情形.

3.1）n3（u）＝3.由斷言，d（u）＝dH（u）＝5，且對(duì)任意的y∈N′（u），當(dāng)d（y）＝3時(shí)，對(duì)任意的x∈N′（y），有dH（x）≥5.假設(shè)d（u1）＝d（u2）＝d（u3）＝3，則dH（u4）≥4，dH（u5）≥4.因?qū)θ我獾膞∈N′（u1）∪N′（u3）有dH（x）≥5，且由 R2）可知，對(duì)任意的fi∈｛f1，f2｝，τ（u→fi）≤1；對(duì)任意的fi∈｛f，f｝，τ（u→f）≤；以及τ（u→f）≤.因此，35j4w′（u）≥4－2×1－2×－＝0.假設(shè)d（u）＝1d（u2）＝d（u4）＝3，則dH（u3）≥4，dH（u5）≥4.因?qū)θ我獾膞∈N′（u1）∪N′（u2）∪N′（u4）有dH（x）≥5，且由 R2）可知，對(duì)任意的fi∈｛f2，f3，f4，f5｝，τ（u→f）≤.因此，w′（u）≥4－1－4×＝0.i

3.2）n3（u）＝2.假設(shè)d（u1）＝d（u2）＝3且對(duì)任意的ui∈｛u3，u4，u5｝，dH（ui）≥4，則由 R2），對(duì)任意的f∈｛f，f｝，τ（u→f）≤.故w′（u）≥4－3×1i34i－2×＝0.假設(shè)d（u）＝d（u）＝3且對(duì)任意的u13i∈｛u2，u4，u5｝，dH（ui）≥4.因 G 不含 A1.4），u1，u3的鄰點(diǎn)中至多只有一個(gè)是度為4.因此，由R2），τ（u→f）＋τ（u→f）≤1＋＝，τ（u→f）＋152τ（u→f）≤1＋＝，τ（u→f）≤.故w′（u）≥434－2×－＝0.3.3）n3（u）≤1.由 R2），w′（u）≥4－2×1－3×＝.

2 無(wú)圈邊色數(shù)

本節(jié)討論不含3圈和5圈相鄰的平面圖的無(wú)圈邊色數(shù)，其中定理的證明需要用到以下幾個(gè)引理.

引理2［5］若G是Δ≤3的圖，則a′（G）≤5.

引理3［6－7］若G 是一個(gè)Δ≤4的圖，則a′（G）≤6.

假設(shè)c是G的一個(gè)無(wú)圈邊k染色，所用的色集為C＝｛1，2，…，k｝.對(duì)任意的v∈V（G），用C（v）表示在染色c下與v相鄰的邊所染的色集合.若一個(gè)圈（或路）的邊是用i和j進(jìn)行染色的，則稱這樣的圈為（i，j）圈（或路）.

定理1 若G是不含3圈和5圈相鄰的平面圖，則a′（G）≤Δ＋2.

證 對(duì)邊數(shù)｜E（G）｜進(jìn)行歸納證明.若｜E（G）｜≤Δ＋2，則G顯然是無(wú)圈邊（Δ＋2）可染的.假設(shè)G是不含3圈和5圈相鄰的平面圖，且有｜E（G）｜≥Δ＋3.若Δ≤4，則由引理2，3知結(jié)論成立.現(xiàn)假設(shè)Δ≥5且G是2連通的.由引理1，G含以下子構(gòu)型A1）～A6）.易見(jiàn)A1）～A6）均含有一條邊滿足d（u）＋d（v）≤8或者d（v）＝2.令H＝G－uv，則H 是一個(gè)不含3圈和5圈相鄰的平面圖，且有Δ（H）≥Δ－1≥4.由歸納假設(shè)或者引理2或3知，H 有一個(gè)無(wú)圈邊（Δ＋2）染色c，其中所用的色集為C＝｛1，2，…，k｝.因d（u）＋d（v）≤8或d（v）＝2，且｜C｜＝Δ＋2≥max｛7，Δ｝，故C＼（C（u）∪C（v））≠?.

若C（u）∩C（v）＝?，則可用C＼（C（u）∪C（v））中的色給uv染色.若對(duì)任意的i∈C（u）∪C（v），存在某個(gè)j∈C＼（C（u）∪C（v）） ，H 不含（i，j）（u，v）路，則可用j染uv.于是假設(shè)

a）C（u）∩C（v）≠?.

b）對(duì)于任意的j∈C＼（ C（u）∪C（v）），存在某個(gè)i∈C（u）∩C（v），使得 H 含有（i，j）（u，v）路.

若G 中含 A1），A2.1），A2.2），A2.4），或者 A4）～A6），則如文獻(xiàn)［12］中 A1），A2.1）～A2.3），或 A3）～A5）的證明一樣，可得到G的一個(gè)無(wú)圈邊染色.若G中含 A2.3）或 A3），則如文獻(xiàn)［11］中 A2.3）或 A3）的證明一樣，可得到G的一個(gè)無(wú)圈邊染色.

［1］Fiamˇcik F.The acyclic chromatic class of a graph［J］.Math Slovaca，1978，28（2）：139.

［2］Alon N，Sudakov B，Zaks A.Acyclic edge colorings of graphs［J］.J Graph Theory，2001，37（3）：157.

［3］Alon A，McDiarmid C，Reed B.Acyclic coloring of graphs［J］.Random Structures Algorithms，1991，2（3）：277.

［4］Esperet L，Parreau A.Acyclic edge－coloring using entropy compression［J］.European J Combin，2013，34（6）：1019.

［5］Basavaraju M，Chandran L S.Acyclic edge coloring of subcubic graphs［J］.Discrete Math，2008，308（24）：6650.

［6］Basavaraju M，Chandran L S.Acyclic edge coloring of graphs with maximum degree 4［J］.J Graph Theory，2009，61（3）：192.

［7］Wang Weifan，Shu Qiaojun，Wang Yiqiao.Every 4－regular graph is acyclically edge－6－colorable［J］.http：／／arxiv.org／abs／1209.2471v1，to be published.

［8］Basavaraju M，Chandran L S，Cohen N，et al.Acyclic edge－coloring of planar graphs［J］.SIAM J Discrete Math，2011，25（2）：463.

［9］Wang Weifan，Shu Qiaojun，Wang Yiqiao.A new upper bound on the acyclic chromaticindices of planar graphs［J］.European J Combin，2013：34（2）：338.

［10］Shu Qiaojun，Wang Weifan，Wang Yiqiao.Acyclic chromatic indices of planar graphs with girth at least four［J］.J Graph Theory，2013，73（4）：386.

［11］Wang Weifan，Shu Qiaojun，Wang Yiqiao.Acyclic edge coloring of planar graphs without 4－cycles［J］.J Comb Optim，2013，25（4）：562.

［12］Shu Qiaojun，Wang Weifan，Wang Yiqiao.Acyclic edge coloring of planar graphs without 5－cycles［J］.Discrete Appl Math，2012，160（7／8）：1211.

［13］Wang Yiqiao，Shu Qiaojun，Wang Weifan.The acyclic edge coloring of planar graphs without a 3－cycle adjacent to a 4－cycle［J］.Discrete Appl Math，2013，161（16／17）：2687.

［14］Pang Shiyou，Miao Lianying，Qu Jibin，et al.On 3－choosability of planar graphs without certain cycles［J］.徐州師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，25（4）：8.