單圈圖的D(2)-點可區(qū)別邊染色

賈秀卿, 李沐春

(蘭州交通大學(xué) 應(yīng)用數(shù)學(xué)研究所, 蘭州 730070)

1 引言與主要結(jié)果

本文所討論的圖均為簡單無向連通圖.一個圖G對應(yīng)于一個有序三元組(V,E,φ), 其中V(G)表示圖G的頂點集,E(G)表示圖G中與V(G)不相交的邊集,φ(G)表示圖G頂點集與邊集的關(guān)聯(lián)函數(shù), 使得對?e∈E(G),u,v∈V(G), 有φ(e)=uv, 此時稱u和v相鄰,u和v是邊e的兩個端點, 同時也稱u和v分別與e相關(guān)聯(lián).若圖G中的兩條邊e1和e2僅有一個公共端點, 則稱e1與e2相鄰.與頂點x關(guān)聯(lián)邊的數(shù)目稱為頂點x的度數(shù), 記為d(x).稱Δ(G)=max{d(x)|x∈V(G)}為圖G的最大度, 簡記為Δ.圖G中度數(shù)為1的頂點稱為懸掛點, 與懸掛點相鄰的點稱為次懸掛點.點u和v之間的距離定義為圖G中最短的(u,v)路長, 記為d(u,v).一個邊數(shù)等于點數(shù)的簡單連通圖稱為單圈圖.圖G中最短圈的長稱為圖G的圍長, 記為g(G).圖G的一個正常k-邊染色是指映射f:E→{1,2,…,k}, 使得對任意兩條相鄰的邊e1和e2, 均有f(e1)≠f(e2).一個頂點x∈V在f下的色集合Sf(x)是指所有與x關(guān)聯(lián)的邊在f下的顏色構(gòu)成的集合.

特別地, 當(dāng)β=2時,D(β)-點可區(qū)別邊染色稱為D(2)-點可區(qū)別邊染色.如果兩個距離不超過2的頂點u,v在D(2)-點可區(qū)別邊染色函數(shù)f下滿足Sf(u)≠Sf(v), 則稱u與v在f下是D(2)-點可區(qū)別的.

基于文獻(xiàn)[9], 本文考慮單圈圖在2-距離以內(nèi)的D(2)-點可區(qū)別邊染色.用數(shù)學(xué)歸納法并結(jié)合Hall定理, 得到如下結(jié)論:

定理1設(shè)G是圍長為g的非圈單圈圖,C是G中唯一的圈.如果G滿足下列條件:

1) 當(dāng)Δ(G)=3時, 圈上只有一個3度點,g≡0(mod 3)且次懸掛點在圈上; 或圈上有至少兩個3度點且任意兩個3度點的距離至少為3;

2) 當(dāng)Δ(G)=4時, 任意兩個4度點的距離至少為3且不包含如圖1所示的S5作為子圖;

圖1 圖S5Fig.1 Graph of S5

3) 當(dāng)Δ(G)≥5時, 任意兩個最大度點的距離至少為3.

2 引 理

引理3[4]設(shè)Cp(p≥3)是一個階數(shù)為p的圈, 則

引理5[4]對至少3階的樹T, 有

引理6(Hall定理)[10]設(shè)G為具有二分類(X,Y)的二部圖, 則G包含飽和X的每個頂點的匹配當(dāng)且僅當(dāng)|N(S)|≥|S|對所有S?X成立.

引理7設(shè)G是圍長為g的單圈圖,Cg為G中唯一的圈.如果Δ(G)=3且圈Cg上僅有一個3度點, 則

情形1)g≡0(mod 3).

若G的次懸掛點在圈Cg上, 則x必為G的懸掛點.設(shè)f1:E(G)→{1,2,3}為G的一個正常邊染色.先用顏色1,3,2對邊v1v2,…,vgv1進(jìn)行循環(huán)染色, 然后用3色染邊v1x.顯然f1是G的一個3-D(2)-VDEC.

考慮如圖2所示的圖G1和G2, 其中圖G1是圈Cg懸掛一條邊v1x的單圈圖, 圖G2是一棵包含懸掛邊v1x且最大度不超過3的樹.

圖2 圖G1和G2Fig.2 Graphs of G1 and G2

注意到粘合圖G1和G2中的邊v1x可得到所需的圖G.下面分別考慮圖G1和G2的D(2)-VDEC.對于圖G1, 因為其次懸掛點恰好在圈上, 故染色f1是G1的一個3-D(2)-VDEC.對于圖G2, 由引理5知, 4種色可以對其進(jìn)行D(2)-VDEC, 記該染色方案為f2.不妨設(shè)f2(v1x)=3,f2(xw1)=4.若w2存在, 不妨設(shè)f2(xw2)=1, 再用{2,4}中的顏色染它的其余關(guān)聯(lián)邊.

為證明圖G是4色可染的, 只需驗證圖G1和G2在上述染色方案不變的條件下粘合邊v1x后仍滿足2距離之內(nèi)的點的色集合不同即可.定義圖G的一個正常邊染色f*為: 對于?z∈E(G),

根據(jù)f*的構(gòu)造可知,

S(v1)={1,2,3},S(v2)={1,3},S(vg)={2,3},

而4∈S(x)∩S(w1), 所以S(x)≠S(v1)≠S(vg)≠S(v2)且S(w1)≠S(v1).如果w2存在, 若dG2(w2)=2, 由于dG(v1)=3, 故S(w2)≠S(v1); 若dG2(w2)=3, 由染色f2知S(w2)={1,2,4}, 故S(w2)≠S(v1).此外,G中的其他點各自在f1與f2下色集合保持不變, 所以仍然滿足D(2)-點可區(qū)別.故f*是圖G的一個4-D(2)-VDEC.

情形2)g?0(mod 3).

當(dāng)圖G中次懸掛點在圈Cg上時, 用顏色1,2,3對邊v1v2,…,vg-2vg-1進(jìn)行循環(huán)染色; 分別用顏色4,2,3染邊vg-1vg,vgv1,v1x.由該染色方案知,v2,v3,…,vg-4的色集合依次循環(huán)等于{1,2},{2,3},{1,3}, 且vg-3,vg-2,vg-1,vg,v1的色集合分別為{1,2},{2,3},{3,4},{2,4},{1,2,3}.易見G中的點都是D(2)-點可區(qū)別的.

當(dāng)圖G中次懸掛點不在圈Cg上時, 證明與g≡0(mod 3)類似, 故略.

注1引理7中, 若圈Cg上僅含一個3度頂點且g≡1(mod 3), 則可得文獻(xiàn)[8]中定理3.11(3).因此, 引理7在一定程度上可視為文獻(xiàn)[8]中定理3.11(3)的推廣.

引理8設(shè)G是圍長為g的非圈單圈圖且GS5(見圖1),C是G中唯一的圈,G中次懸掛點都在圈上.如果G滿足下列條件:

1) 當(dāng)Δ(G)=3時, 圈上只有一個3度點且g≡0(mod 3); 或圈上有至少兩個3度點且G中3度點之間的距離至少為3;

2) 當(dāng)Δ(G)≥4時,G中最大度點之間的距離至少為3.

證明： 令C=v1v2…vgv1.約定i=1時,vi-1表示點vg.令E(vi)E(C)表示與vi關(guān)聯(lián)的不在圈上的邊.下面分四步完成證明.

圖3 圖S5的5-D(2)-點可區(qū)別邊染色Fig.3 5-D(2)-VDEC of graph of S5

2) 證明GS5時下面根據(jù)圍長g分兩種情形討論.

情形①g≠5.

首先對E(C)進(jìn)行染色, 記染色方案為ψ1.按順時針方向, 當(dāng)g≡0(mod 3)時, 用顏色1,2,3依次對邊v1v2,…,vgv1進(jìn)行循環(huán)染色; 當(dāng)g≡1(mod 3)時, 用顏色1,2,3依次對邊v1v2,…,vg-1vg進(jìn)行循環(huán)染色, 用顏色4染邊vgv1; 當(dāng)g≡2(mod 3)時, 用顏色1,2,3依次對邊v1v2,…,vg-5vg-4進(jìn)行循環(huán)染色, 用顏色4,1,2,3,4依次對邊vg-4vg-3,…,vgv1進(jìn)行循環(huán)染色.

其次對E(G)E(C)進(jìn)行染色, 記染色方案為ψ2.在色集合

{1,2,…,Δ+1}{ψ1(vi-1vi),ψ1(vivi+1),ψ1(vi+1vi+2)}

中選取顏色正常染色E(vi)E(C).

注意到在染色ψ1下, 對?i(1≤i≤g), 有vi-1vi,vivi+1,vi+1vi+2三邊不同色.又由染色ψ2知,ψ1(vi+1vi+2)?S(vi), 而ψ1(vi+1vi+2)∈S(vi+1)∩S(vi+2), 故該染色可將vi與vi+1,vi+2的色集合區(qū)分開.因此該染色是圖G的一個D(2)-VDEC.

情形②g=5.

當(dāng)Δ=3時, 由于GS5, 所以至多有4個3度點.注意到因此, 圈C上3度點是4色D(2)-點可區(qū)別的.當(dāng)Δ≥4時.先用顏色1,2,3,4,5依次染C上的邊v1v2,…,v5v1, 再從{1,2,…,Δ+1}除去vi-1vi,vivi+1,vi+1vi+2三邊所染顏色后得到的色集合中選取顏色正常染色E(vi)E(C).易見該染色能使得G中2-距離以內(nèi)的點的色集合可區(qū)別.

情形①g≡0(mod 3).

設(shè)f1:E(C)→{1,2,3}是一個正常邊染色.用顏色1,2,3按順時針方向依次循環(huán)染色v1v2,…,vgv1.設(shè)f2:E(G)E(C)→{1,2,3}是一個正常邊染色.對?x∈E(vi)E(C),f2(x)=α, 其中α滿足

{f1(vi-1vi),f1(vivi+1),α}={1,2,3}.

在f1和f2不變的條件下, 定義圖G的一個正常邊染色f*為

顯然3度點與2度點是D(2)-點可區(qū)別的.此外, 由于3度點之間的距離至少為3, 故其色集合可以相同.對于v2,…,vg,v1, 其在f1下的色集合依次循環(huán)為{1,2},{2,3},{1,3}, 故v1,…,vg中的2度點也是D(2)-點可區(qū)別的.因此,f*即為圖G的一個3-D(2)-VDEC.

情形②g?0(mod 3).

當(dāng)g≡1(mod 3)時.設(shè)G′是圈上恰有兩個3度點的此類單圈圖, 不妨設(shè)d(v1)=d(vm)=3, 其中d(v1,vm)≥3.首先對E(C)進(jìn)行染色.設(shè)染色函數(shù)φ1:E(C)→{1,2,3}.按逆時針方向, 用顏色1,2,3依次對邊v1vg,vgvg-1,…,vm+1vm進(jìn)行循環(huán)染色; 對邊vmvm-1,vm-1vm-2,…,v2v1, 當(dāng)d(v1,vm)?2(mod 3)時, 用顏色2,1,3依次循環(huán)染色, 否則用1,3,2依次循環(huán)染色.

其次對E(G′)E(C)染色.設(shè)染色函數(shù)φ2:E(G′)E(C)→{1,2,3}.對?x∈E(vi)E(C),φ2(x)=α, 其中α滿足

{φ1(vi-1vi),φ1(vivi+1),α}={1,2,3}.

易知φ2是一個正常邊染色.注意到在φ1下, 當(dāng)d(v1,vm)≡0(mod 3)時, 邊v1vg,v2v1,vm+1vm,vmvm-1分別染顏色1,3,1,2; 當(dāng)d(v1,vm)≡1(mod 3)時, 其分別染顏色1,2,3,2; 當(dāng)d(v1,vm)≡2(mod 3)時, 其分別染顏色1,3,2,1.故v1vg與v2v1不同色, 且vm+1vm與vmvm-1不同色.又顯然C上其余邊也滿足相鄰邊染不同色, 所以φ1是C的一個正常邊染色.在φ1和φ2保持不變的條件下, 定義圖G′的一個正常邊染色φ*為

顯然3度點與2度點是D(2)-點可區(qū)別的.由染色φ*知, 對于vg,vg-1,…,vm+1, 其色集合依次循環(huán)為{1,2},{2,3},{1,3}, 故其為D(2)-點可區(qū)別的.對于vm-1,vm-2,…,v2, 當(dāng)d(v1,vm)?2(mod 3)時, 其色集合依次循環(huán)為{1,2},{1,3},{2,3}, 否則循環(huán)為{1,3},{2,3},{1,2}, 故其也是D(2)-點可區(qū)別的.對于vm+1,vm-1, 當(dāng)d(v1,vm)≡0(mod 3)時, 其色集合分別為{1,3},{1,2}; 當(dāng)d(v1,vm)≡1(mod 3)時, 其色集合分別為{2,3},{1,2}; 當(dāng)d(v1,vm)≡2(mod 3)時, 其色集合分別為{1,2},{1,3}.故vm+1與vm-1可區(qū)別.又S(vg)={1,2},S(v2)={1,3}或{2,3}, 故vg與v2也可區(qū)別.因此, 2度點與2度點也滿足D(2)-點可區(qū)別.

設(shè)G是滿足上述條件且至少有3個3度點的單圈圖, 則G′?G.根據(jù)上述證明可知:φ*是圖G′的一個3-D(2)-VDEC.由于圖G是由其子圖G′通過在圈C上添加懸掛邊構(gòu)成的, 故對圖G進(jìn)行染色時, 先用φ*對E(G′)進(jìn)行染色; 再從色集合{1,2,3}中選取顏色正常染新添加的懸掛邊.易見, 此時G中的點仍然滿足D(2)-點可區(qū)別.因此3種顏色可以對圖G進(jìn)行D(2)-VDEC.

(ii) 當(dāng)Δ≥4且G中最大度點之間的距離至少為3時, 根據(jù)圍長g分兩種情形討論.

情形①g≠5.

設(shè)φ1:E(C)→{1,2,…,Δ}是一個正常邊染色.用染色ψ1染圈C.設(shè)φ2:E(G)E(C)→{1,2,…,Δ}是一個正常邊染色.當(dāng)d(vi)=Δ時, 用色集合{1,2,…,Δ}{φ1(vi-1vi),φ1(vivi+1)}中的顏色正常染E(vi)E(C); 當(dāng)3≤d(vi)≤Δ-1時, 用色集合{1,2,…,Δ}{φ1(vi-1vi),φ1(vivi+1),φ1(vi+1vi+2)}中的顏色正常染E(vi)E(C).在φ1和φ2保持不變的條件下, 定義圖G的一個正常邊染色φ*為

顯然兩個度數(shù)不同的點是D(2)-點可區(qū)別的.此外, 由于最大度點之間的距離至少為3, 故其色集合可以相同.對于?i(1≤i≤g), 在染色φ1下, 有vi-1vi,vivi+1,vi+1vi+2三邊不同色.當(dāng)d(vi)<Δ時, 由φ2知,φ1(vi+1vi+2)?S(vi), 而φ1(vi+1vi+2)∈S(vi+1)∩S(vi+2), 故vi與vi+1,vi+2的色集合可區(qū)別.因此φ*是圖G的一個Δ-D(2)-VDEC.

情形②g=5.

首先對E(C)染色.當(dāng)Δ=4時, 不妨設(shè)d(v1)=4, 用顏色1,2,3,4,2依次染v1v2,…,v5v1; 當(dāng)Δ≥5時, 用顏色1,2,3,4,5依次染v1v2,…,v5v1.然后對E(G)E(C)染色.若d(vi)=Δ, 用{1,2,…,Δ}除去vi-1vi,vivi+1兩邊所染顏色后得到的色集合中顏色正常染色E(vi)E(C); 當(dāng)3≤d(vi)≤Δ-1時, 從{1,2,…,Δ}中除去vi-1vi,vivi+1,vi+1vi+2三邊所染顏色后得到的色集合中選取顏色正常染色E(vi)E(C).易見該染色可使得G中2-距離以內(nèi)的點的色集合不同.

4) 證明GS5且不滿足下列條件時有

3 定理1的證明

下面證明定理1.設(shè)C=v1v2…vgv1為單圈圖G中唯一的圈.對任意v∈V(G), 若d(v)≥2且v?V(C), 則稱v為圖G的內(nèi)點, 記圖G的內(nèi)點個數(shù)為p.對任意一個懸掛點x, 設(shè)d(x,C)=min{d(x,u)|u∈V(C)}, 令x0是滿足d(x0,C)=max{d(x,C)}的一個懸掛點.設(shè)v是x0的鄰點, 則v只有一個鄰點w是非懸掛點.令d(v)=k, 其中k≥2.設(shè)x1,x2,…,xk-2是v的除w和x0處的鄰點(如果有), 則有

d(x0)=d(x1)=…=d(xk-2)=1.

設(shè)y1,y2,…,yd(w)-1是w的除v處的鄰點, 不妨設(shè)y1是在圈C到x0的最長路上.

證明： 對p利用數(shù)學(xué)歸納法.當(dāng)p=0時, 由引理8知結(jié)論成立.假設(shè)結(jié)論對內(nèi)點個數(shù)小于p時均成立.設(shè)G有p(p≥1)個內(nèi)點.令G′=G-{x0,x1,…,xk-2}, 其中k≤Δ.由歸納假設(shè)知, (Δ+1)種色(不妨記色集合為S={1,2,…,Δ+1})可以對圖G′進(jìn)行D(2)-VDEC, 記染色方案為f′.不妨設(shè)f′(y1w)=Δ+1.令y2,y3,…,yt是G中與v的度數(shù)相等的點.設(shè)f′(wv)=c1,f′(wyi)=ci, 其中2≤i≤t.下面根據(jù)k分兩種情形將f′延拓為圖G的一個D(2)-點可區(qū)別邊染色f.

情形1)k<Δ.

矛盾.因此T在Y中至少有l(wèi)個相鄰點.由引理6知, 此時存在一個匹配能夠飽和X中的點.從而可選取滿足f(wv)=c1的一個色集合Aj中的顏色去染色與v關(guān)聯(lián)的邊, 使得v與y2,y3,…,yt的色集合可區(qū)別.又因為Δ+1∈Sf(w)∩Sf(y1), 而Δ+1?Sf(v), 故v與y1,w的色集合也可區(qū)別.

情形2)k=Δ.

設(shè)a,b是兩種顏色, 使得a?S(y1)且b?S(w).為保證正常邊染色, 則wv,wyi(2≤i≤t)中至少有(t-1)條邊不染色a.不妨設(shè)為wv,wy2,…,wyt-1.下面在染色f′的基礎(chǔ)上, 通過對v的關(guān)聯(lián)邊進(jìn)行染色并重新染與y2,y3,…,yt關(guān)聯(lián)的邊構(gòu)造染色f.首先令f(wv)=c1,f(wyi)=ci(2≤i≤t); 其次用色集合S{c2}中的顏色正常染v的其余關(guān)聯(lián)邊, 用S{ci+1}中的顏色正常染yi(2≤i≤t-2)的其余關(guān)聯(lián)邊, 用S{c1}中的顏色正常染yt-1的其余關(guān)聯(lián)邊, 用{1,2,…,Δ}中的顏色正常染yt的其余關(guān)聯(lián)邊.由于

{a,b,Δ+1}?Sf(v)∩Sf(yi)(2≤i≤t-1), {a,b}?Sf(yt),

而a?Sf(y1),b?Sf(w),Δ+1?Sf(yt)且c1≠c2≠…≠ct, 故v,w,yi中的點滿足D(2)-點可區(qū)別.

當(dāng)Δ≥5時, 若最大度點之間的距離至少為3, 則p=0時, 由引理8知結(jié)論成立.假設(shè)結(jié)論對內(nèi)點個數(shù)小于p時均成立, 設(shè)G有p(p≥1)個內(nèi)點, 于是G′有一個色數(shù)為Δ(不妨記色集合為S={1,2,…,Δ})的D(2)-點可區(qū)別邊染色f′.令y2,y3,…,yt是G中與v的度數(shù)相等的點.設(shè)f′(wv)=c1,f′(wyi)=ci(2≤i≤t).下面根據(jù)k分3種情形將f′延拓為圖G的一個D(2)-點可區(qū)別邊染色f.

情形1) 2≤k<Δ-1.

矛盾.故T在Y中至少有l(wèi)個相鄰點.由引理6知, 存在一個匹配能夠飽和X中的點.此時選取滿足f(wv)=c1的一個色集合Aj中的顏色去染與v關(guān)聯(lián)的邊.

情形2)k=Δ-1.

當(dāng)d(w)=Δ時, 有d(y1)<Δ.設(shè)a∈{1,2,…,Δ}S(y1).由于d(w)=Δ, 故色a一定出現(xiàn)在w的色集合中.不妨設(shè)f′(wyt)=a, 則邊wv,wy2,…,wyt-1不染色a.下面在染色f′的基礎(chǔ)上, 通過對v,y2,…,yt的關(guān)聯(lián)邊進(jìn)行染色構(gòu)造染色f.首先令f(wv)=c1,f(wyi)=ci(2≤i≤t); 其次用色集合S{c2}中的顏色正常染v的其余關(guān)聯(lián)邊, 用S{ci+1}中的顏色正常染yi(2≤i≤t-2)的其余關(guān)聯(lián)邊, 用S{c1}中的顏色正常染yt-1的其余關(guān)聯(lián)邊, 用S{f′(wy1)}中的顏色正常染yt的其余關(guān)聯(lián)邊.由于a∈Sf(v)∩Sf(yi)(2≤i≤t-1), 而a?Sf(y1), 故f可使得v,yi中的點是D(2)-點可區(qū)別的.

當(dāng)d(w)<Δ時.類似地可得圖G的一個Δ-D(2)-VDEC.

情形3)k=Δ.

顯然v,w,yi中只有v是最大度點, 用色集合S中的顏色正常染v的關(guān)聯(lián)邊即可.

綜上所述, 定理1得證.