邊替換圖的鄰和可區別全染色

常景智,楊 超,姚 兵

(1.上海工程技術大學 數理與統計學院,智能計算與應用統計研究中心,上海 201620; 2.西北師范大學 數學與統計學院,蘭州 730070)

1 引言與預備知識

圖的可區別染色問題是圖論中的研究熱點[1-2],目前已廣泛應用于計算機科學、生命科學以及網絡通信等領域.近年來,關于把點和邊所染顏色相加的可區別染色問題也得到廣泛關注.Karoński等[3]研究了圖的鄰和可區別邊染色,提出了1-2-3猜想.

猜想1(1-2-3猜想)[3]設G為一個階數至少為3的簡單連通圖,則gndiΣ(G)≤3.

Kalkowski等[4]證明了階數至少為3的簡單連通圖的鄰和可區別邊色數不超過5.關于鄰和可區別邊染色的研究目前已有很多結果[5-8].Przybyo等[9]提出了圖的鄰和可區別全染色的概念,并給出了1-2猜想,證明了該猜想對3-點可染色圖、完全圖和四正則圖均成立,且任意簡單連通圖的鄰和可區別全色數不超過11.Kalkowski[10]得到了任意圖的鄰和可區別全色數不超過3.程銀萬等[11]證明了Halin圖的鄰和可區別全色數不超過2.

猜想2(1-2猜想)[9]設G為一個簡單連通圖,則tgndiΣ(G)≤2.

設G和T是兩個簡單圖,i和j為T中的兩個固定頂點,滿足T-i和T-j同構.用T替換圖G的每條邊e=(u,v),使得i=u,j=v,所得圖稱為邊替換圖[12],記為G[T].由定義可知,當T=P3,即T為3個頂點的路且i和j為P3的兩個端點時,G[P3]為圖G的剖分圖,記為S(G); 當T=C3,即T為3個頂點的圈且i和j為C3的兩個端點時,G[C3]為圖G的三角擴展圖,記為R(G).

設圖G=(V(G),E(G))是一個無向簡單圖,若點集S?V(G),且當去掉S后,剩余的子圖G-S中不含任何圈,則S稱為圖G的一個消圈集,同時min{|S||S是圖G的消圈集}稱為圖G的消圈數,記為(G),且此時的消圈集S稱為最小消圈集[13].

定義3[14]設點集D為圖G的一個消圈集.若點集D為一個獨立集,則D稱為圖G的獨立消圈集.

基于上述研究工作,本文首先研究剖分圖和三角擴展圖的鄰和可區別全染色,其次利用獨立消圈集法證明當G為任意圖,且T為星、圈、路、扇、輪以及部分樹時,圖G[T]均滿足1-2猜想.本文涉及的染色均為非正常的,不失一般性,約定證明過程中凡是未被染色的點和邊均染顏色1.

2 剖分圖與三角擴展圖的鄰和可區別全染色

下面介紹獨立消圈集法及樹的鄰和可區別全染色方案.首先,將圖的頂點獨立劃分為森林中的點和獨立消圈集A中的點,森林中各樹之間無連邊,僅森林與獨立消圈集A中的點有連邊; 其次,根據樹的染色算法將森林中的每棵樹染色,保證森林中相鄰頂點權重差不為2.再將獨立消圈集中的點v∈A及其與森林的連邊均染為顏色2,使得該點權重為2d(v)+2; 最后,通過討論森林中點的權重與獨立消圈集A中點的權重是否相等,證明圖是否滿足1-2猜想.

引理1設G是階數至少為3的簡單連通圖.若G中相鄰點的度均不相同,則tgndiΣ(G)=1.

證明: 將圖G中所有邊和點均染顏色1,根據定義2易得點v的權重t(v)=d(v)+1.因為G中相鄰點的度均不相同,所以G中相鄰點權重不同.

引理2設Tn是階數為n的樹,則當n≥3時,

證明: 當Tn中相鄰點的度均不同時,由引理1得tgndiΣ(Tn)=1.當樹Tn中存在度相同的相鄰點時,由于樹是二部圖,不妨設VT=VA∪VB,其中VA,VB分別為A,B兩部的點集合.定義Tn的一個2-全染色如下: 將樹中所有邊染顏色1,設va∈VA,vb∈VB,對于點的染色: 若d(va)≡0(mod 2),則f(va)=1; 若d(va)≡1(mod 2),則f(va)=2; 若d(vb)≡0(mod 2),則f(vb)=2; 若d(vb)≡1(mod 2),則f(vb)=1.因此可知t(VA)為奇數,t(VB)為偶數,相鄰點權重均不相同且權重差不為2,證畢.

定理1設圖G為任意簡單連通圖,則

證明: 當G中無2度點時,S(G)中相鄰點的度均不相同.此時由引理1,將S(G)中所有點和邊均染顏色1,易得相鄰點權重均不相同,即tgndiΣ(S(G))=1.下證當G中存在2度點時,tgndiΣ(S(G))=2.

V(S(G))=V(T1)∪V(T2)∪…∪V(Tn)∪A,

其中Ti(i∈[1,n])為樹,A為獨立消圈集.根據引理2對森林S(G)-A染色,并將獨立消圈集A中的點及其與S(G)-A中點的連邊均染顏色2,由于上述算法證明了樹中每個相鄰點的權重差不為2,所以將獨立消圈集A中的點與S(G)-A的連邊染顏色2后不改變森林中相鄰點的權重.又因為森林中與獨立消圈集A相鄰的點度均為1,故權重不超過5,再由A中點權重最小值為6,易得圖S(G)中相鄰點權重不同.

定理2設圖G為任意簡單連通圖,則當圖G滿足1-2猜想時,有tgndiΣ(R(G))=2.

證明: 將圖G中的點依次標記為vk(k∈[1,n]).對G中的每條邊vivj,通過增加點vij和邊vivij,vijvj(i,j∈[1,n],i≠j),可得三角擴展圖R(G).要證圖R(G)中相鄰點權重不同,只需證R(G)中點vi權重可能的取值數目大于其在圖G中相鄰點vj的個數即可.因為圖G滿足1-2猜想,因此不失一般性,設v1為圖G中的點,d(v1)為點v1的度,根據三角擴展圖定義可知,圖G中的點經過三角擴展后多了d(v1)條邊,把這些邊染顏色1或2,則圖R(G)中點v1的權重有(d(v1)+1)種不同的取值.易見與點v1相鄰點的個數為d(v1)

下證vij與其鄰點權重不同.當G不為K2時,點vij可染為顏色1或2,即點vij權重有兩種可能,并大于其鄰點的個數.由上述證明可知,當G不為K2時,tgndiΣ(R(G))=2; 當G=K2時,R(G)=C3,易得tgndiΣ(C3)=2.

3 幾類邊替換圖的鄰和可區別全色數

定理3設圖G為任意簡單連通圖,則當圖T為Pn(n>3)時,有tgndiΣ(G[Pn])=2.

證明: 當n>3時,圖G[Pn]中必出現相鄰點度相同的情形,故tgndiΣ(G[Pn])≥2.下證當圖G為任意簡單連通圖且圖T為Pn時,tgndiΣ(G[Pn])=2.首先找出圖G[Pn]的一個獨立消圈集A1.由定理1可知,設A1為圖G的一個消圈集,則A1也為圖G[Pn]的一個獨立消圈集.此時將圖G[Pn]的頂點劃分為森林G[Pn]-A1和A1,其中森林內部各樹之間無連邊,僅獨立消圈集A1與森林G[Pn]-A1有連邊.根據引理2中樹的算法對森林G[Pn]-A1染色,該算法證明了樹中每個相鄰點的權重差不為2,故將獨立消圈集A1中的點及其與G[Pn]-A1中點的連邊均染顏色2,從而保證了森林中的各點在加入與A1連邊顏色為2后相鄰點權重仍不同.因為A1中點度最小為2,所以A1中點權重最小值為6.又因為G[Pn]-A1中與獨立消圈集A1相鄰點的度均為1,故其權重不超過5,于是易得圖G[Pn]中相鄰點權重均不相同,即tgndiΣ(G[Pn])=2.

定理4設圖G為任意簡單連通圖,則當圖T為Cn(n>3)時,有tgndiΣ(G[Cn])=2.

證明: 用獨立消圈集法證明結論成立.首先找出圖G[Cn]的一個獨立消圈集A2.根據邊替換圖的定義,i和j為T中的兩個固定頂點,滿足T-i和T-j同構.通過簡單分析可知,當圖T為Cn時,圖T中任意兩點i,j均滿足T-i和T-j同構.為保證可找到圖G[Cn]的一個獨立消圈集A2,不妨取Cn中任意兩個不相鄰的點為固定點,可得邊-圈替換圖G[Cn].取A2=V(G),則V(G[Cn])-V(G)為若干個不交路或孤立點,因此A2為圖G[Cn]的一個獨立消圈集.此時將圖G[Cn]的頂點劃分為森林G[Cn]-A2和A2,其中森林內部無連邊,僅獨立消圈集A2與森林G[Cn]-A2存在連邊.根據引理2中樹的算法對森林G[Cn]-A2染色,該算法證明了樹中每個相鄰點的權重差不為2,故將獨立消圈集A2中的點及其與G[Cn]-A2中點的連邊均染顏色2,從而保證了森林中各點在加入與A2連邊顏色為2后相鄰點權重仍不同.因為A2中點度最小為2,所以A2中點權重最小值為6.又因為G[Cn]-A2中與獨立消圈集A2相鄰點的度均為1,故其權重不超過5,易得圖G[Cn]中相鄰點權重均不同,即tgndiΣ(G[Cn])=2.

定理5設圖G為任意簡單連通圖,則當圖T為(n+1)階星Sn時,有

證明: 星Sn的頂點集和邊集分別表示為

V(Sn)={v1,v2,…,vn,vn+1},

E(Sn)={vivn+1|i=1,2,…,n}.

當n=2時,有S2=P3,G[S2]=S(G),該情形可見定理1.當n>2時,若dG[Sn](v)≠dG[Sn](vn+1),v∈V(G),則經過邊替換后相鄰點度均不相同,因此根據引理1可知tgndiΣ(G[Sn])=1; 若存在點vk∈V(G),使得dG[Sn](vk)=dG[Sn](vn+1)成立,則圖G[Sn]中存在相鄰點度相同的情形,于是可知tgndiΣ(G[Sn])≥2.

下面給出tgndiΣ(G[Sn])=2的染色方案.不妨取星中點v1,vn為固定點,則點vn+1與這兩點均相鄰.根據邊-星替換圖G[Sn]的定義可知,圖Sn中所取固定點必為圖G中的點,不失一般性,記為點v1,將該點本身及關聯邊均染顏色2,可得權重為t(v1)=2d(v1)+2.易見圖G[Sn]-V(G)為森林,根據引理2中樹的算法對森林G[Sn]-V(G)染色,對點vn+1染顏色1或2可保證其權重為奇數,同理對點v2,…,vn染顏色1或2可保證其權重為偶數.由t(v1)=2d(v1)+2≡0(mod 2)知,與v1相鄰的點vn+1權重為奇數,故此時圖G[Sn]中相鄰點權重均不同,即tgndiΣ(G[Sn])=2(n>2).

定理6設圖G為任意簡單連通圖,則當圖T為(n+1)階扇Fn時,有tgndiΣ(G[Fn])=2.

證明: 扇Fn的頂點集和邊集分別表示為

V(Fn)={v1,v2,…,vn,vn+1},

E(Fn)={vivi+1|i=1,2,…,n-1}∪{vivn+1|i=1,2,…,n}.

當n=2時,圖G[F2]=G[C3]=R(G),由定理2可知

tgndiΣ(G[F2])=tgndiΣ(R(G))=2.

下證n>2的情形.根據邊替換圖的定義可知,當圖T為Fn(n>2)時,可取點v1,vn分別為固定點.再由定義知,圖G中的任意兩個鄰點經過邊替換后均有如圖1所示的結構,其中點v1,vn為圖G中的鄰點.要證邊-扇替換圖G[Fn]相鄰點權重不同,只需證圖1結構中相鄰點權重不同,再證兩個相鄰結構中的鄰點權重可區分即可.下面給出全染色方案:

圖1 G[Fn]的結構及其染色Fig.1 Structure and coloring of G[Fn]

根據上述全染色方案可得

易知當n>3時,點vn+1的權重均為奇數,且在n=3時取到最小值8.由

t(v1)=2dG[Fn](v1)+2,t(vn)=2dG[Fn](vn)+2

且

dG[Fn](v1)=dG[Fn](vn)≡0(mod 2),

易見僅當dG[Fn](v1)=dG[Fn](vn)=2時才會出現t(v1)=t(v2)=6或t(vn-1)=t(vn)=6的情形,此時只需將點v1或vn重染為顏色1即可.于是有t(v1)=5≠t(v2)=6或t(vn)=5≠t(vn-1)=6.故圖G[Fn]中相鄰點權重均不同,即tgndiΣ(G[Fn])=2成立.

定理7設圖G為任意簡單連通圖,則當圖T為(n+1)階輪Wn(n>3)時,有tgndiΣ(G[Wn])=2.

證明: 由定理6中扇Fn的定義知,輪Wn的頂點集和邊集分別為

V(Wn)=V(Fn),

E(Wn)=E(Fn)∪{v1vn}.

根據邊替換圖的定義可知,當圖T為Wn時,可取點v1,v3分別為固定點.再由定義知,圖G中的任意兩個鄰點經過邊替換后均有如Wn的結構,其中點v1,v3為圖G中的鄰點.要證邊-扇替換圖G[Wn]相鄰點權重不同,只需證如Wn結構中相鄰點權重不同,再證兩個相鄰結構中的鄰點權重可區分即可.下面給出全染色方案:

根據上述全染色方案可得對應點權重如下:

易知點vn+1的權重均為奇數,而dG[Wn](v1)=dG[Wn](v3),則有

t(v1)=t(v3)=2dG[Wn](v1)+2,

易見t(v1)=t(v3)≡0(mod 2),此時圖G[Wn]中相鄰點權重均不同,即tgndiΣ(G[Wn])=2成立.

定理8設圖G為任意簡單連通圖,若樹Tn中有兩個相鄰的葉子點,則tgndiΣ(G[Tn])=2.

證明: 當圖T為Tn時,根據圖G[Tn]的定義,只需Tn滿足i和j為T中的兩個固定頂點,且圖Tn-i和圖Tn-j同構.

當Tn中有兩個相鄰的葉子點時,不妨設為u1和u2,則Tn-{u1}和Tn-{u2}同構,即圖G[Tn]存在.由于樹Tn是二部圖且不含圈,故易找出圖G[Tn]的一個獨立消圈集A3.此時,將圖G[Tn]的頂點劃分為森林點集V(G[Tn])-A3和獨立消圈集A3,其中森林內部各樹之間無連邊,僅獨立消圈集A3與森林G[Tn]-A3有連邊.利用引理2中的樹染色算法對森林G[Tn]-A3進行染色,該算法證明了樹中每個相鄰點的權重差不為2,故將獨立消圈集A3中的點及其與G[Tn]-A3中點的連邊均染顏色2,從而保證了森林中的各點在加入與A3連邊顏色為2后相鄰點權重仍不同.根據染色規則可知,A3中點權重恒為偶數,又因為獨立消圈集A3中的點在集合G[Tn]-A3中的鄰點權重可利用引理2的證明方法將其調整為奇數,因此圖G[Tn]中相鄰點權重均不同.