若干倍圖的鄰點全和可區別全染色

程銀萬, 楊 超*, 姚 兵

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

圖染色問題是圖論中經典問題之一,其研究成果已被廣泛應用于通信網絡、控制論、計算機科學與編碼理論等領域.由于應用的廣泛性,許多學者在傳統染色的基礎上陸續提出了一系列新染色.2004年,Karoński等提出了圖的鄰和可區別邊染色的概念,并給出了該染色下的1-2-3猜想[1].2021年,Przybylo證明了每個d-正則圖(d≥2)都是鄰和可區別4-邊染色的,且當d≥108時,每個d-正則圖是鄰和可區別3-邊染色的[2].2010年,Przybylo和Wozniak將頂點自身的顏色加入其關聯邊的顏色和中,定義了圖的鄰和可區別全染色,同時給出了基于鄰和可區別全染色的1-2猜想[3].目前,一個較為理想的結果是:任意圖的鄰和可區別全色數不超過3[4].2017年,Flandrin等在鄰和可區別全染色的基礎上,將任意一點的所有鄰點顏色加入其全染色權重和中,提出了圖的鄰點全和可區別全染色的概念[5].注意到,Flandrin等在文獻[5]中僅將圖的鄰點全和可區別全染色與鄰點被擴展和可區別全染色作了一個簡單的對比,并未進行深入研究.近年來,圖的鄰點全和可區別全染色在文獻[6-7]中被進一步研究.受此啟發,本文研究路、圈、星、扇、輪、完全二部圖以及樹的倍圖的鄰點全和可區別全染色問題．

1 預備知識

本文涉及的圖均為連通的簡單圖,V(G)和E(G)分別表示圖G的點集和邊集,d(v)表示圖中頂點v的度.文中未定義的術語和符號均參考文獻[8].下面先介紹與本文有關的定義和概念．

定義1[5]設f：V(G)∪E(G)→[1,k]是圖G的一個k-全染色.定義頂點x的權重函數:

(1)

其中,N(x)={y∈V(G)│xy∈E(G)}.對于任意邊uv∈E(G),若有φ(u)≠φ(v)成立,則稱f是圖G的一個鄰點全和可區別k-全染色(簡記NFSD).圖G的鄰點全和可區別全染色中最小的k值稱為G的鄰點全和可區別全色數,記為fgndiΣ(G)．

定義2[9]設G′是簡單圖G的拷貝,記G的頂點為ui,G′相應的頂點為vi,若圖D(G)滿足:

1)V(D(G))=V(G)∪V(G′);

2)E(D(G))=E(G)∪E(G′)∪{uivj│ui∈V(G),vj∈V(G′),uiuj∈E(G)},

則稱D(G)為G的倍圖．

當n=3時,路P3的倍圖D(P3)如圖1所示.

圖1 倍圖D(P3)Fig.1 Double graph D(P3)

2 主要結論及證明

定理1若圖G中存在度相同的相鄰點,則fgndiΣ(G)≥2．

證明(反證法)假設圖G中存在度相同的相鄰點u,v,即d(u)=d(v).若圖G中的點和邊均染顏色1,則由公式(1)得φ(u)=φ(v)=2d(u)+1=2d(v)+1,與定義1相矛盾,故fgndiΣ(G)≥2．

定理2設Pn=u1u2u3…un表示n(n≥1)階的路,當n=1,3時,fgndiΣ(D(Pn))=1;其他情形,fgndiΣ(D(Pn))=2.

證明由定義2知,當n=1,3時,圖D(Pn)中不存在度相同的相鄰點,所以,當D(Pn)中所有點和邊都染顏色1時,不存在相鄰點權重相同的情況,符合定義1.當n≠1,3時,由定理1知,至少需要2種顏色才可以完成對圖D(Pn)的鄰點全和可區別全染色.下面給出對圖D(Pn)的點和邊的具體染色．

定義D(Pn)的一個全染色f1：V(D(Pn))∪E(D(Pn))→[1,2]如下:

f1(ui)=f1(vi)=1,1≤i≤n,ui,vi∈V(D(Pn));

f1(e)=2,其中,e∈{uiui+1│i≡1,2(mod 4)}∪{vivi+1│i≡0,3(mod 4)};

f1(e0)=1,e0∈E(D(Pn)){e}．

染色f1代入公式(1),可得圖D(Pn)中各點的權重如下.

情形1n≡0(mod 4).

情形2n≡1(mod 4).

情形3n≡2(mod 4).

情形4n≡3(mod 4).

因為各相鄰點權重不同,所以f1為D(Pn)的一個NFSD-2-全染色.

定理3設Cn=u1u2u3…unu1表示階數為n(n≥3)的圈,則fgndiΣ(D(Cn))=2．

證明根據定理1,由于圖D(Cn)中存在度相同的相鄰點,所以至少需要2種顏色才能完成對D(Cn)的鄰點全和可區別全染色.下面分4種情形對D(Cn)的點和邊進行染色．

情形1n≡0(mod 4).

定義D(Cn)的一個全染色f2：V(D(Cn))∪E(D(Cn))→[1,2]如下:

f2(ui)=f2(vi)=1,1≤i≤n,ui,vi∈V(D(Cn));

f2(e)=2,e∈{uiui+1,vivi+1│i≡2,3(mod 4)};

f2(e0)=1,e0∈E(D(Cn)){e}．

由染色f2可得圖D(Cn)中各點的權重如下:

情形2n≡1(mod 4).

定義D(Cn)的一個全染色f3：V(D(Cn))∪E(D(Cn))→[1,2]如下:

ui,vi∈V(D(Cn));f3(e)=2,e∈{uiui+1,vivi+1│i≡1,2(mod 4),i≠1};f3(e0)=1,e0∈E(D(Cn)){e}．

由染色f3可得圖D(Cn)中各點的權重如下:

情形3n≡2(mod 4).

定義D(Cn)的一個全染色f4：V(D(Cn))∪E(D(Cn))→[1,2]如下:

1≤i≤n,ui,vi∈V(D(Cn));f4(e)=2,e∈{uiui+1,vivi+1│i≡0,3(mod 4)};f4(e0)=1,e0∈E(D(Cn)){e}．

由染色f4可得圖D(Cn)中各點的權重如下:

情形4n≡3(mod 4).

定義D(Cn)的一個全染色f5：V(D(Cn))∪E(D(Cn))→[1,2]如下:

ui,vi∈V(D(Cn));f5(e)=2,e∈{uiui+1,vivi+1│i≡0,1(mod 4),i≠1};f5(e0)=1,e0∈E(D(Cn)){e}．

由染色f5可得圖D(Cn)中各點的權重如下:

因為各相鄰點權重不同,所以f2,f3,f4,f5分別為各情形下D(Cn)的一個NFSD-2-全染色.

定理4設Sn表示階數為n+1(n≥3)的星,則fgndiΣ(D(Sn))=1．

證明設Sn的點集和邊集分別為:V(Sn)={u1,u2,…,un+1},E(Sn)={uiun+1│1≤i≤n}.由定義2知,圖D(Sn)為完全二部圖,即D(Sn)=K2,2n.根據定理1,圖D(Sn)中不存在度相同的相鄰點,所以只需要一種顏色就可以完成圖D(Sn)的鄰點全和可區別全染色,即fgndiΣ(D(Sn))=1．

定理5設Fn表示階數為n+1(n≥3)的扇,則fgndiΣ(D(Fn))=2．

證明設Fn的點集和邊集分別為:V(Fn)={u1,u2,…,un+1},E(Fn)={uiun+1│1≤i≤n}∪{uiui+1│1≤i≤n-1}.由定義2知,圖Fn中存在度相同的相鄰點,所以至少需要兩種顏色才可以完成Fn的鄰點全和可區別全染色.具體全染色方案f6：V(D(Fn))∪E(D(Fn))→[1,2]如下:

f6(ui)=f6(vi)=1,1≤i≤n+1;f6(e)=2,e∈{uiui+1,vivi+1│i≡0,1(mod 4)};f6(e0)=1,e0∈E(D(Fn)){e}．

由染色f6可得如下三種情形圖Fn中各點的權重．

情形1n≡0,3(mod 4).

情形2n≡1(mod 4).

情形3n≡2(mod 4).

因為各情形下相鄰點權重不同,所以f6為D(Cn)的一個NFSD-2-全染色．

定理6設Wn表示階數為n+1(n≥3)的輪,則fgndiΣ(D(Wn))=2．

證明設Wn的點集和邊集分別為:V(Wn)={u1,u2,…,un+1},E(Wn)={uiun+1│1≤i≤n}∪{uiui+1│1≤i≤n-1}∪{unu1}.以下分兩種情形證明．

情形1n=3.

定義染色f7：V(D(Wn))∪E(D(Wn))→[1,2]如下:

f7(vi)=1,1≤i≤n+1;f7(e)=2,e∈{u1u2,u1v2,u1v4,u2v4,u3v4,v2v4,v3v4};f7(e0)=1,e0∈E(D(Wn)){e}．

由染色f7可得各點權重如下:

φ(u1)=17,φ(u2)=16,φ(u3)=15,φ(u4)=14,φ(v1)=13,φ(v2)=16,φ(v3)=15,φ(v4)=19．

因為相鄰點權重不同,所以f7為D(W3)的一個NFSD-2-全染色．

情形2n≥4.

1)當n≡0(mod 4)時,定義染色f8：V(D(Wn))∪E(D(Wn))→[1,2]如下:

f(ui)=f(vi)=1,1≤i≤n+1;

f(e)=2,e∈{uiui+1,vivi+1│i≡2,3(mod 4)};

f(e0)=1,e0∈E(D(Cn)){e}．

由染色f8可得各點權重如下:

2)當n≡1(mod 4)時,定義染色f9：V(D(Wn))∪E(D(Wn))→[1,2]如下:

f9(e)=2,e∈{uiui+1,vivi+1│i≡1,2(mod 4),i≠1};f9(e0)=1,e0∈E(D(Wn)){e}．

由染色f9可得各點權重如下:

3)當n≡2(mod 4)時,定義染色f10：V(D(Wn))∪E(D(Wn))→[1,2]如下:

f10(e)=2,e∈{uiui+1,vivi+1│i≡0,3(mod 4)};f10(e0)=1,e0∈E(D(Wn)){e}．

由染色f10可得各點權重如下:

4)當n≡3(mod 4) 時,定義染色f11：V(D(Wn))∪E(D(Wn))→[1,2]如下:

1≤i≤n+1;f11(e)=2,e∈{uiui+1,vivi+1│i≡0,1(mod 4),i≠1};f11(e0)=1,e0∈E(D(Wn)){e}．

由染色f11可得各點權重如下:

因為各情形下相鄰點權重不同,所以f8、f9、f10、f11分別為各情形下D(Cn)的一個NFSD-2-全染色．

定理7設Km,n(m≥1,n≥1)表示完全二部圖,則fgndiΣ(D(Km,n))=2(m=n);fgndiΣ(D(Km,n))=1(m≠n).

證明令V(Km,n)=X∪Y,E(Km,n)={uivj│1≤i≤m,1≤j≤n},其中X={u1,u2,…,um},Y={v1,v2,…,vn}.首先,完成對完全二部圖的鄰點全和可區別全染色,其次,通過倍圖的連接特征發現,完全二部圖Km,n的倍圖D(Km,n)即為完全二部圖K2m,2n.下面分兩種情形證明．

情形1m=n．

定義染色f12：V(Km,n)∪E(Km, n)→[1,2]如下:

f12(ui)=1,f12(vi)=2,f12(uivj)=1,1≤i≤m,1≤j≤n．

由上述染色f12可得各點權重如下:

φ(ui)=3m+1,φ(vi)=2m+2.

觀察發現,僅當m=1時,φ(ui)=φ(vi),而其倍圖K2m,2n的點集X、Y的階數均大于等于2,故對于圖K2m,2n,φ(ui)≠φ(vi)恒成立．

情形2m≠n.

定義染色f13：V(Km,n)∪E(Km,n)→[1,2]如下:

f13(ui)=f13(vi)=f13(uivj)=1,1≤i≤m,1≤j≤n.

由染色f13可知,φ(ui)=2n+1,φ(vi)=2m+1.

所以,此情形下,φ(ui)≠φ(vi)恒成立．

上述兩種情形表明完全二部圖Km,n的鄰點全和可區別全色數是確定的.由于Km,n的倍圖D(Km,n)也是完全二部圖,所以f12和f13分別是各情形下的一種NFSD-全染色．

定理8設T表示n(n≥3)階樹.若樹T中不存在度相同的相鄰點,則fgndiΣ(D(T))=1;若樹T中存在度相同的相鄰點,則fgndiΣ(D(T))=2.

證明當樹T中不存在度相同的相鄰點時,樹的倍圖中也不存在度相同的相鄰點,根據定理1,僅需1種顏色就可以完成樹倍圖的鄰點全和可區別全染色.下面討論樹中存在度相同的相鄰點情形,首先通過構建樹染色算法完成樹的鄰點全和可區別全染色;其次結合樹倍圖的結構特點進行分析證明.樹的鄰點全和可區別全染色算法如下.

步驟1樹T中每個頂點染顏色1．

步驟2對樹T中邊的染色定義如下兩種染色方式.

f14(eu):對頂點u的所有未染色的鄰邊分配顏色2;

f15(eu):對頂點u的一條未染色的鄰邊分配顏色1,其余鄰邊染顏色2．

步驟3選擇樹T中任一度數為奇數的頂點,記為u.即d(u)≡1(mod 2).對u的鄰邊選擇染色方式f14(eu)．

步驟4設ui為點u的鄰點．

當d(ui)≡1(mod 2)時,采用染色方式f15(eui);

當d(ui)≡0(mod 2)時,采用染色方式f14(eui)．

步驟5設uij為點ui的鄰點．當d(ui)≡0(mod 2)時,

若d(uij)≡1(mod 2),采用染色f14(euij);

若d(uij)≡0(mod 2),采用染色f15(euij)．

當d(ui)≡1(mod 2)且f(uiuij)=2時,

若d(uij)≡1(mod 2),采用染色方式f14(euij);

若d(uij)≡0(mod 2),采用染色方式f15(euij)．

當d(ui)≡1(mod 2)且f(uiuij)=1時,

若d(uij)≡1(mod 2),采用染色方式f15(euij);

若d(uij)≡0(mod 2),采用染色方式f14(euij)．

步驟6設uijk為點uij的鄰點．當d(ui)≡1(mod 2)且d(uij)≡1(mod 2)且f(uijuijk)=1時,

若d(uijk)≡0(mod 2),采用染色方式f15(euijk);

若d(uijk)≡1(mod 2),采用染色方式f14(euijk)．

當d(ui)≡1(mod 2)且d(uij)≡1(mod 2)且f(uijuijk)=2時,

若d(uijk)≡0(mod 2),采用染色方式f14(euijk);

若d(uijk)≡1(mod 2),采用染色方式f15(euijk)．

其他情況下的邊染色依照步驟5．

步驟7繼續上述過程,直至樹T的邊都被染了顏色1或2．

完成上述的樹染色過程,樹中相鄰頂點的權重是奇偶可分的,即相鄰點的權重不同.假設樹T′是樹T的復制,其染色方式和樹T保持一致,且樹T和T′之間的連線都染顏色1,觀察樹倍圖的結構發現,此時D(T)中頂點的權重均增加了2d(u)+1,由于2d(u)+1是奇數,所以樹T和T′中的頂點權重的奇偶性均發生了變化.但是,D(T)中相鄰點的權重依然是奇偶可分的,即相鄰點權重不同.假設樹T中的葉子節點為vi,那么染色后圖D(T)中φ(vi)≤6,而與vi相鄰的次結點的權重大于等于9,所以葉子結點的權重小于內點權重恒成立.綜上所述,兩種顏色可以完成D(T)的鄰點全和可區別全染色．