一類仙人掌圖的D(2)-點可區別全染色

汪銀芳, 李沐春, 王國興

(1. 蘭州交通大學 應用數學研究所, 蘭州 730070; 2. 蘭州財經大學 信息工程學院, 蘭州 730020)

0 引 言

本文所考慮的圖均為簡單無向連通圖. 設G=(V,E)是一個圖, 其中V(G)表示圖G的頂點集,E(G)表示圖G的邊集.對?v∈V(G), 記d(u)為頂點v的度,Δ(G)=max{d(u)|u∈V(G)}稱為點u的最大度.特別地, 當d(u)=1時, 點u稱為圖G的懸掛點, 與u關聯的邊稱為懸掛邊.設d(u,v)=min{d(u,v)|u,v∈V(G)}為圖G中點u到點v的距離.若G可以分解成恰好有一個公共頂點v的兩個非空子圖G1和G2, 則點v稱為圖G的分離點.不包含分離點的連通圖稱為塊.仙人掌圖[1]是一個每個塊均為圈或邊的連通圖, 簡記為GT.圈圖Cp(p≥3)的每個點添加一條懸掛邊所得到的圖稱為太陽圖, 記作Sn, 顯然n=2p.設仙人掌圖G的每個塊所構成的集合為B={B1,B2,…,Bm}, 分離點所構成的集合為X={u1,u2,…,un}, 每個塊收縮成點所構成的頂點集為Y={y1,y2,…,ym}.以X和Y構造二部圖B(G)=(X,Y), 對任意的1≤i≤n, 1≤j≤m,ui與yj相鄰當且僅當分離點ui與塊Bj關聯, 此時B(G)稱為圖G的塊樹[2].此外, 塊樹中度為1的頂點對應原圖中的塊稱為端塊[2].如圖1所示, 仙人掌圖GT的分離點為{u1,u2,u3}, 組成仙人掌圖GT的塊為{B1,B2,B3,B4,B5}, 每個塊對應收縮成的點集為{y1,y2,y3,y4,y5}, 構成了塊樹B(GT).

圖1 仙人掌圖GT及其對應的塊樹B(GT)Fig.1 Cactus graph GT and its corresponding block tree B(GT)

目前, 關于圖染色問題的研究已有很多結果.例如: Burris[3]首次提出了圖的點可區別邊染色; Zhang等[4]在點可區別邊染色的概念上, 通過限制頂點的距離提出了圖鄰點可區別邊染色的概念, 即對于一個正常邊染色滿足相鄰點的色集合不相同時稱為圖的鄰點可區別邊染色(也稱為圖的鄰強邊染色); 張忠輔等[5]在正常全染色的基礎上, 提出了D(β)-點可區別全染色, 并給出了路、 圈、 完全圖以及一些聯圖等的D(2)-點可區別全色數.下面給出圖的D(β)-點可區別全染色的概念.

定義1[5]若圖G的一個正常k-全染色f滿足?u,v∈V且1≤d(u,v)≤β時均有C(u)≠C(v), 則f稱為G的一個k-D(β)-點可區別全染色(簡記為k-D(β)-VDTC), 其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.將圖G進行D(β)-點可區別全染色所需顏色的最小值稱為G的D(β)-點可區別全色數, 簡記為χβvt(G).顯然χβvt(G)=min{k|G具有一個k-D(β)-點可區別全染色}.

特別地, 當β=2時,D(β)-點可區別全染色稱為D(2)-點可區別全染色.

猜想1[4-5]對于階至少為2的連通圖G, 有χ2vt(G)≤μ2(G)+1, 其中μG為圖G的2-距離以內的組合全度.

1 預備知識

引理1[5]設Pn(n≥3)是n階的路, 則

引理2[5]設圖Cn是階數為n(n≥3)的圈, 則有

引理3[5]對于圖G, 有χ2vt(G)≥Δ+1; 若G中存在距離不超過2的兩個最大度點, 則χ2vt(G)≥Δ+2.

設f是圖G的一個正常k-全染色, 對?u,v∈V(G), 如果C(u)≠C(v), 則稱u和v在f下是可區別的.顯然如下命題成立.

命題1設f是圖G的一個正常k-全染色, 若d(u)≠d(v), 則u和v在f下是可區別的.

引理4設圖Sn(n≥3)是太陽圖, 則χ2vt(Sn)=5.

證明: 設Cg=v1v2…vgv1(g≥3)為太陽圖Sn的基本圈, 圈上每個點vi關聯的懸掛邊為vixi, 其中懸掛點為xi(1≤i≤g).由引理3可知χ2vt(Sn)≥5.下證Sn有一個5-D(2)-VDTC.令f為V(Sn)∪E(Sn)→{1,2,3,4,5}的一個映射.

當g=3,4,5時, 其染色方案如圖2所示.

圖2 太陽圖的圈長為3,4,5的D(2)-點可區別全染色Fig.2 D(2)-VDTC of solar graph with cycle lengths of 3,4,5

當g≥6時, 分以下4種情形討論:

情形1) 當g≡0(mod 4)時, 染色方案如下: 對于Cg的點vk和邊vkvk+1, 若k≡1(mod 4), 則令f(vk)=1,f(vkvk+1)=4; 若k≡2(mod 4), 則令f(vk)=2,f(vkvk+1)=1; 若k≡3(mod 4), 則令f(vk)=3,f(vkvk+1)=2; 若k≡0(mod 4), 則令f(vk)=4,f(vkvk+1)=3; 對于懸掛邊和懸掛點, 設f(vixi)=5,f(xi)=f(vivi+1), 其中1≤i,k≤g.

情形2) 當g≡1(mod 4)時, 染色方案如下: 對于Cg的點vk和邊vkvk+1, 若k≡1(mod 4), 則令f(vk)=1,f(vkvk+1)=4; 若k≡2(mod 4), 則令f(vk)=2,f(vkvk+1)=1; 若k≡3(mod 4), 則令f(vk)=3,f(vkvk+1)=2; 若k≡0(mod 4), 則令f(vk)=4,f(vkvk+1)=3.其中1≤k≤g-5.而f(vg-4)=1,f(vg-3)=2,f(vg-2)=4,f(vg-1)=1,f(vg)=4;f(vg-4vg-3)=4,f(vg-3vg-2)=1,f(vg-2vg-1)=3,f(vg-1vg)=2,f(vgv1)=3.對于懸掛邊和懸掛點,f(vg-2xg-2)=2,f(vixi)=5(i≠g-2);f(xi)=f(vivi+1), 其中1≤i≤g.

情形3) 當g≡2(mod 4)時, 染色方案如下: 對于Cg的點vk和邊vkvk+1, 若k≡1(mod 4), 則令f(vk)=1,f(vkvk+1)=4; 若k≡2(mod 4), 則令f(vk)=2,f(vkvk+1)=1; 若k≡3(mod 4), 則令f(vk)=3,f(vkvk+1)=2; 若k≡0(mod 4), 則令f(vk)=4,f(vkvk+1)=3.其中1≤k≤g-2.而f(vg-1)=2,f(vg)=5,f(vg-2vg-1)=1,f(vg-1vg)=3.對于懸掛邊和懸掛點, 當1≤i≤g-2時,f(vixi)=5,f(vg-1xg-1)=4,f(vgxg)=2;f(xi)=f(vivi+1)(1≤i≤g).

情形4) 當g≡3(mod 4)時, 染色方案如下: 對于Cg的點vk和邊vkvk+1, 若k≡1(mod 4), 則令f(vk)=1,f(vkvk+1)=4; 若k≡2(mod 4), 則令f(vk)=2,f(vkvk+1)=1; 若k≡3(mod 4), 則令f(vk)=3,f(vkvk+1)=2; 若k≡0(mod 4), 則令f(vk)=4,f(vkvk+1)=3.其中1≤k≤g-3.而f(vg-2)=1,f(vg-1)=3,f(vg)=4,f(vg-2vg-1)=4,f(vg-1vg)=2,f(vgv1)=3.對于懸掛邊和懸掛點,f(vg-1xg-1)=1,f(vixi)=5(i≠g-1);f(xi)=f(vivi+1)(1≤i≤g).

綜上,χ2vt(Sn)=5, 結論成立.

注1在引理4的證明中, 至少存在一個懸掛點與它鄰點在圈上的某條關聯邊染同色; 染色函數f是Sn的基本圈Cg的一個5-D(2)-VDTC.

p階圈圖Cp(p≥3)的點上任意添加懸掛邊所得到的圖稱為破太陽圖.特別地,Cp的每個點上都添加懸掛邊即為太陽圖.記破太陽圖的基本圈為Cp=v1v2…vpv1(p≥3), 圈圖的部分點上添加的懸掛邊為vixi, 其中懸掛點記為xi,i∈{1,2,…,p}.

引理5設圖G是一個破太陽圖, 則有χ2vt(G)≤5.

證明: 設G*是G添加懸掛邊后得到的太陽圖, 顯然,G是G*的一個子圖.由引理4可知,G*存在一個5-D(2)-VDTCf, 同時也是G*的基本圈的一個5-D(2)-VDTC.因此,f|G為G的一個5-D(2)-VDTC.

2 主要結果

定理1設GT為最大度為3的仙人掌圖, 則χ2vt(GT)≤6.

證明: 對仙人掌圖GT的塊數t進行歸納.

顯然t≥2(由于t=1不存在最大度為3的仙人掌圖).當t=2時, 僅有圈上關聯一條懸掛邊的圖滿足最大度為3, 不妨記該仙人掌圖GT上的圈為Cn=u1u2…unu1, 懸掛邊為u1x1, 其中u1是GT的分離點.先給圈Cn著色, 由引理2知, 圈Cn存在一個5-D(2)-VDTCf′, 再從集合{1,2,3,4,5}{f′(u1),f′(u1u2),f′(u1un)}中任選一種顏色染給邊u1x1, 令點x1與邊u1u2染同色, 從而得到圖GT的一個著色方案f.在f中, 圈上的2度點均為D(2)-點可區別的.注意到d(x1)≠d(ui), 其中i=1,2,…,n.由命題1知點x1和點u1與2-距離以內所有點的色集合不同, 因此f是圖GT的一個5-D(2)-VDTC.

假設結論對塊數小于t的仙人掌圖GT都成立.下面考慮GT中t≥3的情形, 設GT的塊樹中最長路為P, 對路P的端點對應GT中的端塊是邊或者是圈, 分以下兩種情形討論.

情形1) 存在一條路P的某個端點對應GT中的端塊是邊.

設該邊為uv, 其中u為分離點, 由歸納假設知GT-uv存在一個6-D(2)-VDTCf′, 在f′的基礎上給邊uv及點v進行染色, 將f′延拓為圖GT的一個6-D(2)-VDTCf.對點u的除v外的任意一個鄰點x, 再分兩種情形討論.

① 點x不屬于路P的某個端點對應GT中的塊.

u除v外至多有兩個鄰點, 不妨設為點x1和x2(如果存在), 其中x1屬于路P中某個端點對應GT中的塊,x2不屬于路P中某個端點所對應GT中的塊, 且點x2不能再關聯其他塊, 否則與邊uv屬于路P最后一個端點對應GT中的塊矛盾, 如圖3所示.記x1除u外的其他鄰點為點y1和y2(如果存在).若給點u重染色不改變x1和x2的色集合, 則可以給u重染色.因為f(u)≠f(ux1),f(u)≠f(x1),f(u)≠f(ux2),f(u)≠f(x2), 故點u可用色至少有6-4=2種; 因為f(uv)≠f(u),f(uv)≠f(ux),f(uv)≠f(ux1), 故邊uv的可用色至少有6-3=3種.從而u至少有2×3=6種可用色集合.為區分u的色集合與至多3個同度點x1,y1,y2的色集合, 可從u的至少6種可用色集合中除去可能與x1,y1,y2的色集合相同的至多3種, 從余下至少3種色集合中任選一種分配給點u及邊uv.因為d(u)≠d(x2),d(u)≠d(v), 故由命題1知u的色集合與點v,x2的色集合可區別.又因為f(v)≠f(uv),f(v)≠f(u), 故點v的可用色有6-2=4種,d(v)=d(x2)=1, 從v的可用色集合中除去可能與x2的色集合相同的那種, 再從余下的至少3種可用色集合中任選一種分配給點v, 則點v與2-距離的同度點x2的色集合可區別, 于是有χ2vt(GT)≤6.

圖3 x2不屬于最長路Fig.3 x2 does not belong to the longest path

② 點x屬于路P中某個端點對應GT中的塊.

此時, 與點u相鄰的點x至多有2個.

(i)x的個數為1.

此時, 根據d(u)=2或3, 以及d(x)=2或3分3種情形, 其中點u在2-距離內至多有2個同度點, 如圖4所示.由于f(uv)≠f(u),f(uv)≠f(ux), 所以邊uv可用色有6-2=4種, 從uv的4種可用色中除去使得點u與至多2個同度點色集合相同的那2種色, 再從剩下的至少2種可用色中任選一種分配給邊uv, 再從集合{1,2,3,4,5,6}{f(uv),f(u)}中任選一種染給點v.d(v)≠d(u),d(v)≠d(x), 由命題1知點v與2-距離內的點的色集合都不同.

圖4 x∈P且有1個xFig.4 x∈P and has one x

(ii)x的個數為2, 如圖5所示.

圖5 x∈P且有2個xFig.5 x∈P and has two x

此時d(u)=3,u的除v外的2個鄰點記為x1,x2, 記點x1,x2在圈上除點u外的鄰點為y1,y2.點x1,x2,y1,y2可以關聯其他的塊, 但是都至多只能關聯一個塊, 否則uv所在塊樹的路就不是最長路; 且點x1,x2,y1,y2關聯的塊只能是邊, 否則Δ>3.

為證明GT是6色可染的, 只需驗證G1和G2在上述染色方案不變的前提下粘合邊w3w后仍滿足2-距離之內的點的色集合不同即可.記構造得到的GT全染色為

(1)

情形2) 任意一條路P的某個端點對應GT中的端塊是圈.

如圖6所示, 由于Δ=3, 故與最后一個圈關聯的塊只能為邊.設u1為塊樹中某一條最長路的最后一個分離點,Cm=u1u2…umu1(m≥3)是GT的塊樹中最長路的某端點對應的端塊, 點u1的除u2和um的鄰點記為y, 點y除鄰點u1外, 至多還有2個鄰點不妨設為y1和y2.

圖6 最后一個塊為圈Fig.6 The last block is cycle

為證明GT是6色可染的, 只需驗證G1和G2在上述染色方案不變的前提下粘合邊zw后仍滿足2-距離之內的點的色集合不同即可.記構造得到的GT的全染色為式(1).