平面圖的無圈邊染色

王藝橋，舒巧君

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

0 引言

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

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

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

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

本文旨在研究不含3圈和5圈相鄰的平面圖的無圈邊色數.將證明此類圖也是滿足猜想1的，這在一定程度上改進了文獻［11－12］中的結果和擴充了［13］中的結果.

1 結構分析

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

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

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

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

A1.2）d（u）＝d（v）＝3，且x是v的第三個鄰點；

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 的鄰點；

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

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

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）且對于i＝3，4，n2（ui）＝d（ui）－4；

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

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

A4）一個5點u相鄰于4個3點v，x，y，z以及另一個點w.

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

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

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

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

因為G不含A1.1），沒有5－點會與2點相鄰，亦即，若u是滿足3≤d（u）≤5的點，則dH（u）＝d（u）.類似地，若d（u）≥6且n2（u）＝0，則dH（u）＝d（u）.又因為G 不含A2.1）和 A2.2），每個6＋點u至多相鄰于d（u）－4個2點，這也說明了：若d（u）≥6且n2（u）≥1，則dH（u）≥4，dH（u）＝d（u）－n2（u）.

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

斷言1 Δ（H）≥3，對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 設f＝［uvw］是一個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，且對任意的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）.又因為G 不含 A4）和 A1.5），所以，b）成立.

斷言6 設u∈V（H），若d（f1）＝3，則對于任意的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.

用權轉移方法來得出矛盾.首先，由歐拉公式｜V（H）｜－｜E（H）｜＋｜F（H）｜＝2和關系式

易得到如下等式：

其次，定義權函數w：對于u∈V（H），w（u）＝2dH（u）－6；對于f∈F（H），w（f）＝dH（f）－6.由（1）可得權和為－12.接下來，將定義權轉移規則R1）～R2），且將按此規則對權進行轉移.一旦權轉移完成，就會產生新的權函數w′.然而，在權轉移的過程中，權和是保持不變的.不過可以證明對于所有的x∈V（H）∪F（H）均有w′（x）≥0.這就導出了一個很明顯的矛盾

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

設u是H 中一個度為k的點.令τ（u→f）表示從點u轉到與其相關聯面f的權的量.權轉移規則定義如下：

R2）設k≥5.

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

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

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

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

假設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.

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

假設d（f）＝5，則w（f）＝d（f）－6＝－1.由R1.1）或 R2.1），b（f）上 的4＋點至少給 f 權.若n＋（f）≥4，則w′（f）≥－1＋4×＝0.否則，因G4不含 A1.2），再由斷言1，不妨設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.

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

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

假設dH（u）≥9，則

假設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，故

假設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.

假設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，因此

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

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

情況1 m3（u）＝3.由斷言6，可設d（f1）＝d（f2）＝d（f4）＝3且d（f3）≥6，d（f5）≥6.因G 不含 A2.4），A5）和 A6），且由斷言5知，f1，f2，f4中至多只有兩個面的最小度為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，則由對稱性，只需討論以下3種子情形.

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

3.2）n3（u）＝2.假設d（u1）＝d（u2）＝3且對任意的ui∈｛u3，u4，u5｝，dH（ui）≥4，則由 R2），對任意的f∈｛f，f｝，τ（u→f）≤.故w′（u）≥4－3×1i34i－2×＝0.假設d（u）＝d（u）＝3且對任意的u13i∈｛u2，u4，u5｝，dH（ui）≥4.因 G 不含 A1.4），u1，u3的鄰點中至多只有一個是度為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 無圈邊色數

本節討論不含3圈和5圈相鄰的平面圖的無圈邊色數，其中定理的證明需要用到以下幾個引理.

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

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

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

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

證 對邊數｜E（G）｜進行歸納證明.若｜E（G）｜≤Δ＋2，則G顯然是無圈邊（Δ＋2）可染的.假設G是不含3圈和5圈相鄰的平面圖，且有｜E（G）｜≥Δ＋3.若Δ≤4，則由引理2，3知結論成立.現假設Δ≥5且G是2連通的.由引理1，G含以下子構型A1）～A6）.易見A1）～A6）均含有一條邊滿足d（u）＋d（v）≤8或者d（v）＝2.令H＝G－uv，則H 是一個不含3圈和5圈相鄰的平面圖，且有Δ（H）≥Δ－1≥4.由歸納假設或者引理2或3知，H 有一個無圈邊（Δ＋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染色.若對任意的i∈C（u）∪C（v），存在某個j∈C＼（C（u）∪C（v）） ，H 不含（i，j）（u，v）路，則可用j染uv.于是假設

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

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

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

［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］.徐州師范大學學報：自然科學版，2007，25（4）：8.