2-外平面圖的無圈邊色數(shù)*

舒巧君， 王維凡

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

0 引言

本文僅考慮有限簡單圖．給定一個圖G，用V(G)，E(G)，Δ(G)，δ(G)和g(G)分別表示它的頂點(diǎn)集、邊集、最大度、最小度和圍長;對于一個頂點(diǎn)x∈V(G)，令dG(x)表示x在G中的度，稱度為k(至少為k，至多為k)的頂點(diǎn)為k-點(diǎn)(k+-點(diǎn)，k--點(diǎn));N(v)表示點(diǎn)v的鄰點(diǎn)集合，并用Ni(v)表示點(diǎn)v的鄰點(diǎn)中度為i的頂點(diǎn)的集合，ni(v)(ni+(v)，ni-(v))表示點(diǎn)v的鄰點(diǎn)中度為i(至少為i，至多為i)的頂點(diǎn)的個數(shù)．若能將圖G畫在平面上，使得它的邊僅在端點(diǎn)處相交，則稱G是可平面圖．圖的這種平面上的畫法稱為圖的平面嵌入，或稱平面圖．

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

無圈邊染色的概念最早是由Alon等［1］提出的，他們證明了:對任何圖G，有a'(G)≤64Δ(G)．Molly等［2］將這個界改進(jìn)到 a'(G)≤16Δ(G);2007 年，Muthu 等［3］證明了當(dāng) g(G)≥220 時，a'(G)≤4．52Δ(G);2001年，Alon等［4］還提出了如下著名的無圈邊染色猜想:

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

猜想1至今還未得到證實(shí)，僅知道一些特殊圖類滿足該猜想．Alon等［5］證明了確定任意圖G的無圈邊色數(shù)是一個NP-問題．關(guān)于正則圖、平面圖、完全二部圖等特殊圖的無圈邊色數(shù)研究可參閱文獻(xiàn)［6-11］．最近，筆者考慮了大圍長平面圖的無圈邊色數(shù)，證明了:若存在(k，m)∈{(3，11)，(4，8)，(5，7)，(8，6)，(12，5)}，使得 Δ(G)≥k，g(G)≥m，則 a'(G)=Δ(G)．

本文研究2-外平面圖的無圈邊染色問題．一個平面圖被稱為2-外平面圖，如果它能嵌入平面使得其所有頂點(diǎn)出現(xiàn)在至多2個面的邊界上．2-外平面圖是對外平面圖的一種推廣．關(guān)于2-外平面圖的結(jié)構(gòu)性質(zhì)及相關(guān)參數(shù)的研究可參閱文獻(xiàn)［12-13］．

1 結(jié)構(gòu)性質(zhì)

先建立2-外平面圖的一些結(jié)構(gòu)性質(zhì)，為無圈邊染色做準(zhǔn)備工作．

引理1［12］設(shè)G是一個連通的2-外平面圖，Δ(G)≥5，δ(G)≥2，則G含有下列子結(jié)構(gòu)之一:

(A1)一個2-點(diǎn)相鄰于一個8--點(diǎn);

(A2)一個4-圈v1v2v3v4v1帶有一條弦v1v3，使得dG(v2)=dG(v3)=dG(v4)=3;

(A3)一個 4-圈 w1w2w3w4w1帶有一條弦 w1w3，使得 dG(w3)=3，dG(wi)≤5，i=1，2，4;

(A4)一個 5-圈 x1x2x3x4x5x1帶有 2 條弦 x1x3，x1x4，使得 dG(x3)=dG(x4)=3，dG(xi)≤6，i=1，2，5．

利用引理1，可以證得引理2．

引理2 設(shè)G是一個連通的2-外平面圖，Δ(G)≥5，δ(G)≥2，則G含有下列子結(jié)構(gòu)之一:

(B1)一個2-點(diǎn)v相鄰于點(diǎn)u和w，使得uw?E(G);

(B2)一個2-點(diǎn)v相鄰于點(diǎn)w和一個5--點(diǎn)u，使得uw∈E(G);

(B3)一個2-點(diǎn)v相鄰于點(diǎn)w和一個6+-點(diǎn)u，使得uw∈E(G)且n4-(u)≥dG(u)-4;

(B4)一個3-點(diǎn)v相鄰于一個3-點(diǎn)u;

(B5)一個 4-圈 w1w2w3w4w1帶有一條弦 w1w3，使得 dG(w3)=3，dG(wi)≤5，i=1，2，4．

證明 假設(shè)結(jié)論不成立，則存在連通的2-外平面圖G不含(B1)～(B5)．由假設(shè)條件知，δ(G)≥2，Δ(G)≥5．若一個2-點(diǎn) v相鄰于點(diǎn) u和 w，因 G不含(B1)和(B2)，則必有 uw∈E(G)，且 d(u)≥6，d(w)≥6．更有當(dāng)2≤d(u)≤5時，有N2(u)=?．設(shè)H表示去掉G中所有2-點(diǎn)后所得到的圖，則H仍是一個連通的2-外平面圖，且在G中不與2-點(diǎn)相鄰的點(diǎn)在H中的度不變．

設(shè) u∈V(H)，則u∈V(G)且 3≤dG(u)．若 3≤dG(u)≤5，則由 G 不包含(B1)和(B2)，可推出dH(u)=dG(u)．若dG(u)≥6且 n2(u)≥1，則由 G不含(B3)，必有 n4-(u)≤dG(u)-5，亦有 n2(u)≤dG(u)-5．于是n5+(u)≥5，這隱含著dH(u)≥5，說明H不會產(chǎn)生新的4--點(diǎn)．所以，當(dāng)x∈V(H)時，必有N2(x)=?，且H不會含有(B4)．

假設(shè)dG(u)≥6且 n2(u)≥1．若 n2(u)≤dG(u)-6，則 dH(u)≥6;若 n2(u)=dG(u)-5，則由n5+(u)≥5可得n5+(u)=5，n3(u)=0．所以dH(u)=5，在H中u不會與3-點(diǎn)相鄰，可得 H不會含有(B5)．

綜上所得，連通的2-外平面圖H不含2-點(diǎn)，且不含(A2)，(A3)和(A4)，這和引理1矛盾，所以假設(shè)不成立，即不存在那樣的G．引理2證畢．

2 無圈邊色數(shù)

引理3［11］對每一個 Δ(G)≤4的圖G，有a'(G)≤Δ(G)+3．

定理1 若G為2-外平面圖，則a'(G)≤Δ(G)+3．

證明 設(shè)G是一個2-外平面圖．若Δ(G)≤4，則由引理3即可得到結(jié)論．假設(shè)Δ(G)≥5．對頂點(diǎn)數(shù)和邊數(shù)的和進(jìn)行歸納證明．若|V(G)|+|E(G)|=11，則結(jié)論顯然成立．假設(shè)G是一個2-外平面圖使得|V(G)|+|E(G)|≥12．顯然，可以假設(shè)G是連通的．若G包含一個1-點(diǎn)v，則子圖G-v的任何無圈(Δ(G)+3)-邊染色能被擴(kuò)充到整個圖G．于是，假設(shè)δ(G)≥2．由引理2知，G至少含有子結(jié)構(gòu)(B1)～(B5)之一．接下來分別處理這5種子圖形，并直接應(yīng)用引理2中的記號．此外，簡記Δ=Δ(G)，設(shè)C={1，2，…，Δ+3}表示所用的顏色集合，C(v)表示圖中與點(diǎn)v所關(guān)聯(lián)的邊在某個染色下所用的顏色集合．因?yàn)棣ぁ?，所以可得|C|=Δ+3≥8．

情形1 G含有(B1) 令H=G-v+{uw}．顯然，H仍是一個簡單2-外平面圖，Δ(H)=Δ．由歸納假設(shè)，H有一個無圈(Δ+3)-邊染色c．為了將c擴(kuò)充到到整個圖G，令c(uv)=c(uw)，用a∈CC(w)染vw，G中的其他邊的顏色與在H中對應(yīng)的邊顏色相同．因|CC(w)|≥Δ+3-dG(u)≥3，故這樣的顏色a存在，且染色c仍是無圈的．

情形2G含有(B2) 令H=G-{uv}．由歸納假設(shè)，H有一個無圈(Δ+3)-邊染色c．若c(vw)?C(u)，則用 a∈C(C(u)∪{c(vw)})染 uv;若 c(vw)∈C(u)，則用 b∈C(C(u)∪C(w))染 uv．因|C(C(u)∪C(w))|≥Δ+3-(dG(w)+dG(u)-3)≥Δ+3-(Δ+5-3)≥1，故顏色 b存在，且染色 c仍是無圈的．

情形3G含有(B3) 由情形2，可以假設(shè)d(u)≥6，d(w)≥6．令H=G-{uv}．由歸納假設(shè)，H有一個無圈(Δ +3)-邊染色 c．不妨設(shè) C(u)={1，2，…，dG(u)-1}，c(uw)=1，C1(u)={c(ux)|dG(x)≤4}，C2(u)={c(ux)|dG(x)≥5}．因?yàn)?v是一個2-點(diǎn)，所以|C1(u)|≥dG(u)-5，|C2(u)|≤4．

若c(vw)?C(u)，則用 a∈C(C(u)∪{c(vw)})染 uv．否則假設(shè) c(vw)∈C(u)．若存在 b∈(CC(u))C(w)，則用 b染 uv．進(jìn)一步假設(shè) CC(u)?C(w)．因 dG(w)≥6，故推出 1?C1(u)且|C1(u){1}|=|C1(u)|≥dG(u)-5．

若存在i∈C1(u)C(w)，不妨設(shè)c(uu')=i，其中u'是u的一個滿足dG(u')≤4的鄰點(diǎn)，則用i改染vw，并取j∈(CC(u))C(u')染 uv．特別地，當(dāng) c(vw)∈C1(u)時，可以給 uv類似的染色．因?yàn)閨(CC(u))C(u')|≥Δ+3-(dG(u)-1)-(dG(u')-1)≥Δ+3-(Δ-1)-(4-1)=1，所以顏色 j存在，且染色c仍是無圈的．

現(xiàn)在假設(shè) C1(u)?C(w)且 c(vw)?C1(u)．因1?C1(u)，c(vw)∈C(u)，(CC(u))∩C1(u)=?，故{1，c(vw)}∪(CC(u))∪C1(u)?C(w)，又可得|C(w)|≥|{2，c(vw)}∪(CC(u))∪C1(u)|=2+|CC(u)|+|C1(u)|≥2+(Δ +3-dG(u)+1)+(dG(u)-5)=Δ +1，這與|C(w)|≤d(w)≤Δ 矛盾．

情形4 G含有(B4) 設(shè)v1，v2≠u是v的另外2個頂點(diǎn)，u1，u2≠v是u的另外2個頂點(diǎn)．令H=G-{uv}．由歸納假設(shè)，H 有一個無圈(Δ +3)-邊染色 c，不妨設(shè)c(vv1)=1，c(vv2)=2．若 1，2?C(u)，則用a∈C(C(v)∪C(u))染 uv．因|C(C(v)∪C(u))|≥Δ+3-4=Δ -1≥4，故顏色 a存在，且染色c仍是無圈的．

1)若|C(v)∩C(u)|=1，并設(shè) c(uu1)=1，c(uu2)=3，則用 a∈C(C(v)∪C(u)∪C(v1))染 uv．因|C(C(v)∪C(u)∪C(v1))|≥Δ+3-Δ-2=1，故這樣的a存在，且染色c仍是無圈的．

2)若|C(v)∩C(u)|=2，并設(shè) c(uu1)=1，c(uu2)=2．因 d(v2)≤Δ，故存在 a∈C(C(v2)∪{1})．若不存在u到v的雙色路，則用a染uv．否則，用a改染vv2，然后轉(zhuǎn)化為1)的情形．

情形5 G含有(B5) 不失一般性，假設(shè)dG(wi)=5(i=1，3，4)，否則討論會更簡單些．令H=G-{w1w3}．由歸納假設(shè)，H 有一個無圈(Δ +3)-邊染色 c．不妨設(shè) c(w2w3)=1，c(w3w4)=2，并令 X=C(w2){c(w1w2)，c(w2w3)}，Y=C(w1){c(w1w2)，c(w1w4)}，Z=C(w4){c(w1w4)，c(w3w4)}．顯然，|X|=|Z|=3，|Y|=2．由對稱性知，只需考慮以下子情形．

1)1，2?C(w1)．只需用 C(C(w1)∪{1，2})中的某色染 w1w3．

2)1，2∈C(w1)．不妨設(shè) C(w1)={1，2，3，4}，且令 S={5，6，…，Δ +3}．因 c是 H 的無圈邊染色，故c(w1w2)=2和c(w1w4)=1不能同時成立．若c(w1w2)=2，則只需用a∈SX染w1w3;若c(w1w4)=1，則有類似的討論．于是，假設(shè)c(w1w2)=4且c(w1w4)=3，亦即Y={1，2}．

若存在 a∈S(X∪Z)，則用 a染 w1w3．于是，假設(shè) S?X∪Z．因|X|=|Z|=3且|S|=|{5，6，…，Δ +3}|≥4，故{1，2，3，4}中至多有2 個屬于X∪Z．若{1，2，3，4}中沒有顏色屬于X∪Z，則用3 染w1w3，用S中的某色改染w1w4．假設(shè){1，2，3，4}中至少有1個屬于X∪Z，則分下面幾種子情形加以討論:

①假設(shè)1，4∈Z．不妨設(shè) Z={1，4，5}，于是 X={6，7，8}，則用6 染 w1w3，3 改染 w2w3．若2，3∈X，則有類似的討論．

②假設(shè)1，4?Z．不妨設(shè)Z={5，6，7}，于是8∈X，則用8 改染 w3w4，{5，6，7}X 中的某色染 w1w3．若2，3?X，則有類似的討論．

③假設(shè)|{1，4}∩Z|=1 且|{2，3}∩X|=1，此時 Δ =5．不妨設(shè) X={a，5，6}，Z={b，7，8}，其中 a∈{2，3}，b∈{1，4}．當(dāng) a=3 時，用5 染 w1w3，7 改染 w2w3;當(dāng) b=4 時，有類似的討論．于是，假設(shè) a=2 且b=1．因此，可用7 染 w1w3，4 改染 w3w4，8 改染 w2w3．

3)1∈C(w1)且2?C(w1)．不妨設(shè) C(w1)={1，3，4，5}，有 2 種子情形需要考慮:

①c(w1w4)=1．設(shè) c(w1w2)=3，Y={4，5}．若存在 a∈{6，7，…，Δ +3}在 X∪Z 出現(xiàn)至多一次，則用a 染 w1w3;否則推出 Δ =5 且 X=Z={6，7，8}．因此，可用4 改染 w2w3，5 改染 w3w4，2 改染 w1w3．

②c(w1w4)≠1．設(shè) c(w1w2)=3，c(w1w4)=4，Y={1，5}．若存在 a∈{6，7，…，Δ +3}X，則用 a 染w1w3;否則推出 Δ =5 且 X={6，7，8}．此時用 4 改染 w2w3．若存在 b∈{6，7，8}，則用 b染 w1w3;否則推出 Z={6，7，8}．因此，可用1 改染 w3w4，2 染 w1w3．定理 1 證畢．

定理1中的上界Δ(G)+3似乎不是緊的．當(dāng)最大度較大時不難將這個界改進(jìn)到Δ(G)+2，從而使猜想1對有較大最大度的2-外平面圖成立．因此，證明猜想1對所有2-外平面圖成立和回答下面問題是有意義的:

問題1 是否存在一個常數(shù)C，使得當(dāng)一個2-外平面圖G滿足Δ(G)≥C時，有a'(G)=Δ(G)?

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

［2］Molly M，Reed B．Further aogorithmic aspects of Lovász local lemma［C］//Proceedings of the 30thAnnual ACM Symposium on Theory of Computing Held in Dallas，TX．New York:ACM，1998:524-529．

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

［4］Alon N，Sudakov B，Zaks A．Acyclic edge colorings of graphs［J］．J Graph Theory，2001，37(3):157-167．

［5］Alon N，Zaks A．Algorithmic aspects of acyclic edge coloring［J］．Algorithmica，2002，32(4):611-614．

［6］Něsetril J，Wormald N C．The acyclic edge chromatic number of a randomd-regular graph is d+1［J］．J Graph Theory，2005，49(4):69-74．

［7］Fiedorowics A，Haluszczak M，Narayanan N N．About acyclic edge colourings of planar graphs［J］．Inform Process Lett，2008，108(6):412-417．

［8］Hou J，Wu J，Liu G，et al．Acyclic edge colorings of planar graphs and series-parallel graphs［J］．Sci China Ser:A Math，2009，51(3):605-616．

［9］Borowiecki M，F(xiàn)iedorowics A．Acyclic edge colouring of plananr graphs without short cycles［J］．Discrete Math，2010，310(9):1445-1455．

［10］Basavaraju M，Chandran L S．A note on acyclic edge coloring of complete bipartite graphs［J］．Discrete Math，2009，309(13):4646-4648．

［11］Basavaraju M，Chandran L S．Acyclic edge coloring of graphs with maximum with degree 4［J］．J Graph Theory，2009，61(3):192-209．

［12］湯宇翔，王維凡．2-外平面圖的 L(2，1)-標(biāo)號數(shù)［J］．浙江師范大學(xué)學(xué)報:自然科學(xué)版，2009，32(1):40-44．

［13］孔立，張秀麗．雙外平面的全染色［J］．山東輕工業(yè)學(xué)院學(xué)報，2005，19(2):81-84．