系列平行圖和Meredith圖的無循環(huán)邊著色

張衛(wèi)標(biāo)，謝德政

(1.商丘學(xué)院 計算機工程學(xué)院，河南 商丘 476000；2.重慶大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，重慶400044)

1 引言和預(yù)備知識

本文考慮有限、無向的簡單圖.設(shè)圖G=(V，E)，分別用 V(G)、E(G)、Δ(G)和 δ(G)表示圖 G 的頂點集、邊集、最大度和最小度，EG(v)、dG(v)和NG(v)分別表示G中與頂點v關(guān)聯(lián)的邊集、頂點v的度和與v相鄰的頂點的集合.圖G的無循環(huán)邊著色是一個映射c：E(G)→C={1，2，…，k}，滿足

(i)c(uv)≠c(vw)，uv、uw∈E(G)；

(ii)圖G中不含雙色圈.

圖G的無循環(huán)邊色數(shù)是指對圖G進(jìn)行無循環(huán)邊著色所用的最少的色數(shù)，記作a′(G).

圖G的無循環(huán)邊著色是在無循環(huán)著色的基礎(chǔ)上研究的，Alon等[1]提出猜想：對任意圖G，有a′(G)≤Δ(G)+2，并且證明了a′(G)≤64Δ(G).之后，關(guān)于圖的無循環(huán)邊色數(shù)取得了很多成果[2-8].文獻(xiàn)[2]證明了a′(G)≤16Δ(G).文獻(xiàn)[3]證明了對于非正則連通圖G，當(dāng)Δ(G)=3時，a′(G)=3或4.文獻(xiàn)[4]證明了對任意偽 Halin 圖 G，當(dāng) Δ(G)≠3 時，有 a′(G)= Δ(G).文獻(xiàn)[5]證明了對任意平面圖 G，a′(G)≤Δ(G)+25.文獻(xiàn)[6]對幾類特殊圖證明了Alon猜想.文獻(xiàn)[7]證明了完全二部圖 Kp2，p2滿足a′(Kp2，p2)≤Δ(Kp2，p2)+2，p為奇素數(shù).文獻(xiàn)[8]研究了一些星圖的無循環(huán)邊色數(shù).本文基于圖的結(jié)構(gòu)性質(zhì)，利用數(shù)學(xué)歸納法和構(gòu)造法研究系列平行圖和Meredith圖的無循環(huán)邊著色.

定義1[9]在圖G的邊uw上插入一個頂點v(v?V(G))，得到的圖 G*稱為 G的一個剖分圖，其中V(G*)=V(G)∪{v}，E(G*)=E(G){uw}∪{uv，vw}.如果 H1、H2是同一個圖的剖分圖，則稱這2個圖是同胚的.

定義2[9]若圖G不含與K4同胚的子圖，則稱圖G為系列平行圖(series-parallel graph)，簡稱為SP圖.

定義3設(shè)(u，v)是圖G的以頂點u為起點，以頂點v為終點的一條路，若從頂點u開始依次用顏色α、β給路(u，v)上的邊交替著色，則這樣的路稱為雙色路(u，α，β，v).

定義4設(shè)c是圖G的一個邊著色，(u，v)是圖G的以頂點u為起點，以頂點v為終點的一條雙色路(u，α，β，v)，若 c(uu′)=c(v′v)= α 或 β，其中 uu′、v′v是路上的邊，則稱這條路為關(guān)鍵雙色路(u，α，β，v).

定義5[9]設(shè)Petersen圖的外圈頂點集和內(nèi)圈頂點集分別為{p0，p1，p2，p3，p4}和{t0，t1，t2，t3，t4}.與 pi、ti相對應(yīng)的完全二部圖Kk-1，k(k≥2)的二分劃分別為Xi、Yi和 Ui、Vi，其中：

i=0，1，2，3，4.按如下方式用Kk-1，k(k≥2)取代Petersen圖的每個頂點，連接

得到的k正則圖稱為Meredith圖，記為Gk.

引理[10]設(shè)G是最小度不小于2的SP圖，則下述情況至少有一種成立.

(1)G中存在2個相鄰的2度點.

(2)G中存在一個3-圈xuvx，使得dG(x)=2，dG(u)=3，dG(v)≥3.

(3)G中存在一個4-圈uxvyu，使得dG(x)=dG(y)=2，且min{dG(u)，dG(v)}≥3.

(4)G中存在含頂點y的3-圈xyux和zyvz，使得dG(x)=dG(z)=2，dG(y)=4，且min{dG(u)，dG(v)}≥3.

2 主要結(jié)果

定理 1設(shè)圖 G 為 SP圖，Δ(G)=5，δ(G)≥2，則a′(G)≤6.

證明對圖G的邊數(shù)|E(G)|使用數(shù)學(xué)歸納法.設(shè)C={1，2，…，6}，由引理知|E(G)|≥7.當(dāng)|E(G)|=7時，由圖的結(jié)構(gòu)可知結(jié)論成立.設(shè)當(dāng)|E(G)|＜m(m≥8)時，結(jié)論成立，下面證明當(dāng)|E(G)|=m時，結(jié)論成立.

(1)若圖G中存在2個相鄰的2度頂點x、y，NG(x)={u，y}，NG(y)={v，x}，構(gòu)造新圖G*=G-{x}+uy.顯然|E(G*)|＜ m，由歸納假設(shè)，G*可以用 6種顏色進(jìn)行無循環(huán)邊著色，設(shè)為c*，下面將c*擴充為圖G的一個無循環(huán)邊著色c.令c(ux)=c*(uy)，c(xy)=α，α∈{1，2，…，6}{c(ux)，c(yv)}.由于 c(ux)≠c(yv)，因此邊ux、xy、yv不著雙色，故在圖G中不存在關(guān)鍵雙色路(u，c(ux)，c(yv)，v)，這樣即得圖 G 的一個無循環(huán)邊著色c，故a′(G)≤6.

(2)若圖G中存在一個3-圈xuvx，使得dG(x)=2，構(gòu)造新圖 G*=G-ux.顯然Δ(G*)=5，下面證明當(dāng)dG(v)=5時，結(jié)論成立，則當(dāng)dG(v)＜5時，結(jié)論自然成立.

事實上，由歸納假設(shè)，G*可以用6種顏色進(jìn)行無循環(huán)邊著色，設(shè)為 c*，下面將 c*擴充為c.令c(ux)=μ，μ∈{1，2，…，6}{c*(uv)，c*(vx)，c*(uy)}，因為u是一個3度頂點，y是與u相鄰的另一個頂點.這樣在G中無雙色圈，即得圖G的一個無循環(huán)邊著色c，故a′(G)≤6.

(3)若圖G中存在一個4-圈uxvyu，使得dG(x)=dG(y)=2，且min{dG(u)，dG(v)}≥3.若uv∈E(G)，則與(2)類似可證結(jié)論成立.若 uv?E(G)，令 G*=G-{y}+uv.顯然 Δ(G*)=5，下面證明當(dāng) dG(u)=5 且dG(v)=5 時，結(jié)論成立，則當(dāng) dG(u)＜ 5 或 dG(v)＜ 5時，結(jié)論自然成立.

事實上，由歸納假設(shè)，G*存在一個用了6種顏色的無循環(huán)邊著色c*，下面擴充c*為c.令c(vy)=c*(uv)，c(uy)=γ，γ∈{1，2，…，6}{c*(uz)}，其中uz∈EG(u).因為c(ux)≠c(uy)≠c(vy)，即在G中無雙色圈，即得圖G的一個無循環(huán)邊著色c，故a′(G)≤6.

定理 2設(shè)圖 G 為 SP圖，Δ(G)≥5，δ(G)≥2，則a′(G)≤Δ(G)+1.

證明對圖G的邊數(shù)|E(G)|和最大度Δ(G)做雙重數(shù)學(xué)歸納法.設(shè) C={1，2，…，Δ(G)+1}，由圖的結(jié)構(gòu)性質(zhì)有|E(G)|≥Δ(G)+2.當(dāng)|E(G)|= Δ(G)+2時，結(jié)論顯然成立.當(dāng)Δ(G)=5時，由定理1得結(jié)論成立.設(shè)當(dāng)|E(G)|＜ m(m ＞ Δ(G)+2)或 Δ(G)＜ n(n≥6)時，結(jié)論成立.下面證明當(dāng)|E(G)|=m或Δ(G)=n時，結(jié)論成立.

(1)若圖G中存在2個相鄰的2度頂點x、y，NG(x)={u，y}，NG(y)={v，x}，設(shè) G*=G-{x}+uy.顯然 Δ(G*) = Δ(G)且|E(G*)|＜ m，由歸納假設(shè) G*可以用Δ(G*)+1種顏色進(jìn)行無循環(huán)邊著色，設(shè)為c*，下面擴充c*為c.令c(ux)=c*(uy)，c(xy)=ρ，ρ∈{1，2，…，Δ(G)+1}{c(ux)，c(yv)}，由于 c(ux)≠c(yv)，因此邊ux、xy、yv不著雙色，故在圖G中不存在關(guān)鍵雙色路(u，c(ux)，c(yv)，v)，即得圖 G 的一個無循環(huán)邊著色c，故a′(G)≤Δ(G)+1.

(2)若G中存在一個3-圈xuvx，使得dG(x)=2，令 G*=G-ux.顯然 Δ(G*)=n 且|E(G*)|＜ m，由歸納假設(shè)，G*可以用Δ(G)+1種顏色進(jìn)行無循環(huán)邊著色，設(shè)為c*，下面擴充c*為c，c是一個Δ(G)+1種顏色的無循環(huán)邊著色，證明當(dāng)dG(v)=Δ(G)時，結(jié)論成立，則當(dāng)dG(v)＜Δ(G)時，結(jié)論自然成立.

事實上，令 c(ux)= τ，τ∈{1，2，…，Δ(G)+1}{c*(uv)，c*(vx)，c*(uy)}，因為u是一個3度頂點，y是與u相鄰的另一個頂點.這樣在圖G中無雙色圈，即得圖G的一個無循環(huán)邊著色c，故a(′G)≤Δ(G)+1.

(3)若 G 中存在一個 4-圈 uxvyu，使得 dG(x)=d(Gy)=2，且min{d(Gu)，d(Gv)}≥3.若uv∈E(G)，則與(2)類似可證.若 uv?E(G)，令 G*=G-{y}+uv.顯然 Δ(G*)=n且|E(G)*|＜m，下面證明dG(*u)=Δ(G)且dG(*v)=Δ(G)時，結(jié)論成立.

由歸納假設(shè)，G*存在一個用Δ(G)+1種顏色的無循環(huán)邊著色c*，擴充c*為c.令c(vy)=c(*uv)，c(uy)=φ，φ∈{1，2，…，Δ(G)+1}{c(*uz)}，其中uz∈E(Gu).因為 c(ux)≠c(uy)≠c(vy)，這樣在 G 中無雙色圈，即得圖G的一個用了Δ(G)+1種顏色的無循環(huán)邊著色c，故a(′G)≤Δ(G)+1.

定理3設(shè)Gk是Meredith圖，則a(′Gk)=Δ(Gk).

證明由于完全二部圖Kk-1，k是Gk的一個子圖，故 a′(Kk-1，k)≤a′(Gk).設(shè) X、Y 是完全二部圖 Kk-1，k的二分劃，其中 X={x1，x2，…，xk-1}，Y={y1，y2，…，yk}.設(shè)

EKk-1，(kx)i={ei，1，ei，2，…，ei，k}i=1，2，…，k-1構(gòu)造完全二部圖Kk-1，k的邊著色h：E(Kk-1，)k→{1，2，…，k}.設(shè)C=(ci)j(k-1)×k，D=(di)j(k-1)×k，其中：

在圖Kk-1，k中，令h(ci)j=dij，容易驗證h為圖Kk-1，k的一個無循環(huán)邊著色.

下面只需給出Gk的一個無循環(huán)邊著色c：E(Gk)→{1，2，…，k}.對Meredith圖中的每一個完全二部圖 Kk-1，k均用同樣的方式 h 進(jìn)行著色，c|Kk-1，k=h，然后對 Kk-1，k中的 k-1 度頂點 w 的關(guān)聯(lián)邊 e(e?E(Kk-1，k))進(jìn)行著色，c(e)={1，2，…，k}{c(EKk-1，(kw))}.此時，在Gk中，任意以2個這樣的邊為起始邊和終邊的路之間至少有2條著不一樣顏色的邊，故不會形成雙色圈.這樣就得到了Meredith圖的一個無循環(huán)邊著色，所以a(′Gk)=Δ(Gk).

參考文獻(xiàn)：

[1]ALON N，SUDAKOV B，ZAKS A.Acyclic edge coloring of graphs[J].Journal of Graph Theroy，2001，37(3)：157-167.

[2]ALON N，ZAKS A.Algorithmic aspects of acyclic edge colorings[J].Algorithmica，2002，32(4)：611-614.

[3]BASAVAARAJUM，CHANDRANLS.Acyclicedgecoloringof subcubic graphs[J].Discrete Mathematics，2008，308(24)：6650-6653.

[4]張衛(wèi)標(biāo)，段志霞.偽Halin圖的無循環(huán)邊著色[J].河南師范大學(xué)學(xué)報(自然科學(xué)版)，2010，38(2)：13-15.ZHANGWB，DUANZX.Acyclicedgecoloringofpseudo Halin-Graphs[J].JournalofHenanNormalUniversity(NaturalScience)，2010，38(2)：13-15(in Chinese).

[5]BASAVARAJU M，CHANDRAN S，COHEN N，et al.Acyclic edgecolorings of planar graphs[J].Siam Journal on Discrete Mathematics，2011，24(6)：463-478.

[6]WANG T，ZHANG Y.Acyclic edge coloring of graphs[J].Discrete Applied Mathematics，2014，167(4)：290-303.

[7]VENKATESWARLU A，SARKAR S，ANANTHANARAYANAN SM.On acyclic edge-coloring of complete bipartite graphs[J].Discrete Mathematics，2017，340(3)：481-493.

[8]SHANASBABU P，CHITHRA A V.A note on acyclic edge colouring of star graph families[J].American Journal of Computational Mathematics，2015，5(3)：253-257.

[9]閻立軍，王淑棟，馬芳芳.系列平行圖和Meredith圖的關(guān)聯(lián)著色[J].高校應(yīng)用數(shù)學(xué)學(xué)報，2008，23(4)：481-486.YAN L J，WANG S D，MA F F.Incidence colorings of series-parallel graphsandMeredithgraphs[J].AppliedMathematicsAJournalofChinese Universities，2008，23(4)：481-486(in Chinese).

[10]吳建良.系列平行圖的列表顏色[J].山東大學(xué)學(xué)報(自然科學(xué)版)，2000，35(2)：144-149.WU J L.List edge-colouring of series-parallel graphs[J].Journal of Shandong University(Natural Science Edition)，2000，35(2)：144-149(in Chinese).