程銀萬, 楊 超*, 姚 兵

(1.上海工程技術(shù)大學(xué)數(shù)理與統(tǒng)計(jì)學(xué)院, 智能計(jì)算與應(yīng)用統(tǒng)計(jì)研究中心, 上海 201620;2.西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 蘭州 730070)

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

1 預(yù)備知識

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

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

(1)

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

定義2[9]設(shè)G′是簡單圖G的拷貝,記G的頂點(diǎn)為ui,G′相應(yīng)的頂點(diǎn)為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的倍圖．

當(dāng)n=3時(shí),路P3的倍圖D(P3)如圖1所示.

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

2 主要結(jié)論及證明

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

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

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

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

定義D(Pn)的一個(gè)全染色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)中各點(diǎn)的權(quán)重如下.

情形1n≡0(mod 4).

情形2n≡1(mod 4).

情形3n≡2(mod 4).

情形4n≡3(mod 4).

因?yàn)楦飨噜忺c(diǎn)權(quán)重不同,所以f1為D(Pn)的一個(gè)NFSD-2-全染色.

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

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

情形1n≡0(mod 4).

定義D(Cn)的一個(gè)全染色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)中各點(diǎn)的權(quán)重如下:

情形2n≡1(mod 4).

定義D(Cn)的一個(gè)全染色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)中各點(diǎn)的權(quán)重如下:

情形3n≡2(mod 4).

定義D(Cn)的一個(gè)全染色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)中各點(diǎn)的權(quán)重如下:

情形4n≡3(mod 4).

定義D(Cn)的一個(gè)全染色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)中各點(diǎn)的權(quán)重如下:

因?yàn)楦飨噜忺c(diǎn)權(quán)重不同,所以f2,f3,f4,f5分別為各情形下D(Cn)的一個(gè)NFSD-2-全染色.

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

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

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

證明設(shè)Fn的點(diǎn)集和邊集分別為:V(Fn)={u1,u2,…,un+1},E(Fn)={uiun+1│1≤i≤n}∪{uiui+1│1≤i≤n-1}.由定義2知,圖Fn中存在度相同的相鄰點(diǎn),所以至少需要兩種顏色才可以完成Fn的鄰點(diǎn)全和可區(qū)別全染色.具體全染色方案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中各點(diǎn)的權(quán)重．

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

情形2n≡1(mod 4).

情形3n≡2(mod 4).

因?yàn)楦髑樾蜗孪噜忺c(diǎn)權(quán)重不同,所以f6為D(Cn)的一個(gè)NFSD-2-全染色．

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

證明設(shè)Wn的點(diǎn)集和邊集分別為: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可得各點(diǎn)權(quán)重如下:

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

因?yàn)橄噜忺c(diǎn)權(quán)重不同,所以f7為D(W3)的一個(gè)NFSD-2-全染色．

情形2n≥4.

1)當(dāng)n≡0(mod 4)時(shí),定義染色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可得各點(diǎn)權(quán)重如下:

2)當(dāng)n≡1(mod 4)時(shí),定義染色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可得各點(diǎn)權(quán)重如下:

3)當(dāng)n≡2(mod 4)時(shí),定義染色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可得各點(diǎn)權(quán)重如下:

4)當(dāng)n≡3(mod 4) 時(shí),定義染色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可得各點(diǎn)權(quán)重如下:

因?yàn)楦髑樾蜗孪噜忺c(diǎn)權(quán)重不同,所以f8、f9、f10、f11分別為各情形下D(Cn)的一個(gè)NFSD-2-全染色．

定理7設(shè)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}.首先,完成對完全二部圖的鄰點(diǎn)全和可區(qū)別全染色,其次,通過倍圖的連接特征發(fā)現(xiàn),完全二部圖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可得各點(diǎn)權(quán)重如下:

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

觀察發(fā)現(xiàn),僅當(dāng)m=1時(shí),φ(ui)=φ(vi),而其倍圖K2m,2n的點(diǎn)集X、Y的階數(shù)均大于等于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的鄰點(diǎn)全和可區(qū)別全色數(shù)是確定的.由于Km,n的倍圖D(Km,n)也是完全二部圖,所以f12和f13分別是各情形下的一種NFSD-全染色．

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

證明當(dāng)樹T中不存在度相同的相鄰點(diǎn)時(shí),樹的倍圖中也不存在度相同的相鄰點(diǎn),根據(jù)定理1,僅需1種顏色就可以完成樹倍圖的鄰點(diǎn)全和可區(qū)別全染色.下面討論樹中存在度相同的相鄰點(diǎn)情形,首先通過構(gòu)建樹染色算法完成樹的鄰點(diǎn)全和可區(qū)別全染色;其次結(jié)合樹倍圖的結(jié)構(gòu)特點(diǎn)進(jìn)行分析證明.樹的鄰點(diǎn)全和可區(qū)別全染色算法如下.

步驟1樹T中每個(gè)頂點(diǎn)染顏色1．

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

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

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

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

步驟4設(shè)ui為點(diǎn)u的鄰點(diǎn)．

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

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

步驟5設(shè)uij為點(diǎn)ui的鄰點(diǎn)．當(dāng)d(ui)≡0(mod 2)時(shí),

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

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

當(dāng)d(ui)≡1(mod 2)且f(uiuij)=2時(shí),

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

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

當(dāng)d(ui)≡1(mod 2)且f(uiuij)=1時(shí),

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

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

步驟6設(shè)uijk為點(diǎn)uij的鄰點(diǎn)．當(dāng)d(ui)≡1(mod 2)且d(uij)≡1(mod 2)且f(uijuijk)=1時(shí),

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

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

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

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

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

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

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

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