程銀萬, 楊 超, 姚 兵

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

1 引言與預(yù)備知識

本文考慮的圖G=(V,E)均為簡單、 無向、 連通圖.設(shè)[n]表示正整數(shù)集合{1,2,…,n},dG(v)和δ(G)分別表示一個點(diǎn)v的度和圖G的最小度.用NG(x)或N(x)表示圖G中頂點(diǎn)x的鄰點(diǎn)集合.本文涉及的其他概念可參見文獻(xiàn)[1].

猜想1[2]對于階數(shù)至少為3的任意連通圖G, gndi∑(G)≤3.

Kalkowski等[3]證明了若G是k-可著色的且k為奇數(shù), 則G中存在一個鄰和可區(qū)別k-邊染色.因此, 對于一類3-可著色圖, 包括二部圖, 猜想1成立; Addario-Berry等[4]給出了當(dāng)k=30時, 每個無孤立邊的圖都有一個鄰和可區(qū)別k-邊染色; 進(jìn)一步， 文獻(xiàn)[5]和文獻(xiàn)[6]分別將k值改進(jìn)到k=15和k=13; 對于每個無孤立邊的圖, Kalkowski等[3]還證明了其都是鄰和可區(qū)別5-邊染色的; Przybylo[7]證明了每個d-正則圖(d≥2)都是鄰和可區(qū)別4-邊染色的, 且當(dāng)d≥108時, 每個d-正則圖都是鄰和可區(qū)別3-邊染色的.

Przybylo等[8]在鄰和可區(qū)別邊染色的基礎(chǔ)上考慮加上點(diǎn)自身的顏色, 定義了圖的鄰和可區(qū)別全染色.設(shè)f:V(G)∪E(G)→[k]為圖G的一種非正常k-全染色.對于每個頂點(diǎn)x, 設(shè)

t(x)=f(x)+σ(x).

如果圖G中的任意相鄰頂點(diǎn)x和y滿足t(x)≠t(y), 則稱f為圖G的一個鄰和可區(qū)別全染色(NSDT).圖G的NSDT-k-全染色中最小值k稱為圖G的鄰和可區(qū)別全色數(shù), 記為tgndi∑(G).進(jìn)一步, Przybylo等[8]給出了關(guān)于鄰和可區(qū)別全染色的1-2猜想:

猜想2[8]對于任何連通圖G, tgndi∑(G)≤2.

當(dāng)圖G是一個3-可著色圖、 完全圖或者4-正則圖時[8], 猜想2成立.Kalkowski[9]給出了一個較理想的結(jié)果: 對于每個圖G, tgndi∑(G)≤3.Flandrin等[10]考慮將頂點(diǎn)的顏色加入到其鄰點(diǎn)和鄰邊的權(quán)重和中, 提出了圖的鄰點(diǎn)全和可區(qū)別全染色.

設(shè)f:V(G)∪E(G)→[k]表示圖G的一個非正常k-全染色.定義權(quán)重函數(shù)

如果對任意邊xy∈E(G), 都有φ(x)≠φ(y), 則稱f為圖G的一個鄰點(diǎn)全和可區(qū)別k-全染色(NFSD).圖G的NFSD-k-全染色中最小值k稱為圖G的鄰點(diǎn)全和可區(qū)別全色數(shù), 記為fgndi∑(G).

設(shè)T是至少有4個頂點(diǎn)的樹, 則樹T中的頂點(diǎn)或者是度為1的點(diǎn)(稱為葉子), 或者是度至少為3的點(diǎn).哈林圖H=T∪C是用圈C順次連接樹T中的所有葉子而得到的一類平面圖.通常稱T為哈林圖的特征樹,C稱為其伴隨圈.設(shè)V0?V(H)V(C), 且V0中的每個點(diǎn)均與圈C上的頂點(diǎn)相鄰.設(shè)V1是V0的子集, 且滿足V1中每個頂點(diǎn)的鄰邊中(dG(v)-1)條鄰邊與葉子相連.

本文先對特征樹T進(jìn)行邊染色, 并給伴隨圈C的邊分配顏色, 證明1-2-3猜想對哈林圖成立; 再對特征樹T進(jìn)行全染色, 并給伴隨圈C的邊E(C)分配顏色, 證明1-2猜想對哈林圖也成立； 最后對特征樹T進(jìn)行全染色, 并給伴隨圈C的邊E(C)進(jìn)行調(diào)色, 得到哈林圖的鄰點(diǎn)全和可區(qū)別全色數(shù)至多為3.

2 哈林圖的1-2-3猜想

算法1

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

f1(ev): 對頂點(diǎn)v的所有未染色鄰邊分配顏色3;

f2(ev): 對頂點(diǎn)v的未染色鄰邊之一分配顏色2, 其余鄰邊都染顏色3.

步驟2) 選擇點(diǎn)集V1中一個最小度點(diǎn)并標(biāo)記其為v.初始地, 對v與葉子相鄰的一條邊染顏色2,v的其余鄰邊都染顏色3.

步驟3) 設(shè)vi是頂點(diǎn)v的鄰點(diǎn).如果點(diǎn)vi度的奇偶性與點(diǎn)v度的奇偶性不同, 則采用染色方式f2(evi)對vi鄰邊進(jìn)行染色; 否則, 采用染色方式f1(evi).

步驟4) 設(shè)vij是頂點(diǎn)vi的鄰點(diǎn).當(dāng)σ(vi)=3dH(vi), 且點(diǎn)vij度的奇偶性與點(diǎn)vi度的奇偶性不同時, 采用染色方式f1(evij)對vij的鄰邊進(jìn)行染色; 否則, 采用染色方式f2(evij).

當(dāng)σ(vi)=3dH(vi)-1,f(vivij)=2, 且點(diǎn)vij度的奇偶性與點(diǎn)vi度的奇偶性不同時, 采用染色方式f1(evij); 否則, 采用染色方式f2(evij).如果f(vivij)=3, 且點(diǎn)vij度的奇偶性與點(diǎn)vi度的奇偶性不同時, 則采用染色方式f2(evij); 否則, 使用染色方式f1(evij).

步驟5) 設(shè)vijk是頂點(diǎn)vij的鄰點(diǎn).當(dāng)σ(vij)=3dH(vij), 且點(diǎn)vijk度的奇偶性與點(diǎn)vij度的奇偶性不同時, 采用染色方式f1(evijk)； 否則, 采用染色方式f2(evijk).

當(dāng)σ(vij)=3dH(vij)-1,f(vijvijk)=2, 且點(diǎn)vijk度的奇偶性與點(diǎn)vij度的奇偶性不同時, 采用染色方式f1(evijk)； 否則, 采用染色方式f2(evijk).如果f(vijvijk)=3, 且點(diǎn)vijk度的奇偶性與點(diǎn)vij度的奇偶性不同時, 則采用染色方式f2(evijk)； 否則, 采用染色方式f1(evijk).

當(dāng)σ(vij)=3dH(vij)-2,f(vijvijk)=2, 且點(diǎn)vijk度的奇偶性與點(diǎn)vij度的奇偶性不同時, 采用染色方式f2(evijk)； 否則, 采用染色方式f1(evijk).如果f(vijvijk)=3, 且點(diǎn)vijk度的奇偶性與點(diǎn)vij度的奇偶性不同時, 則采用染色方式f1(evijk)； 否則, 采用染色方式f2(evijk).

步驟6) 繼續(xù)上述過程, 直到T中所有的邊都被分別標(biāo)注2和3.

定理1設(shè)H=T∪C為哈林圖, 則gndi∑(H)≤3.

證明: 首先利用算法1證明可以用顏色2和3完成對任意樹T的鄰和可區(qū)別邊染色.

設(shè)Cm=x1x2…xmx1是伴隨圈.xiyj是邊集E(H)中的邊, 其中xi∈V(Cm),yj∈V0, 1≤i≤m, 1≤j≤|V0|, 且下標(biāo)i和j分別表示對m和|V0|取模.由算法1知, 樹T中所有相鄰點(diǎn)權(quán)重的奇偶性不同.對于點(diǎn)集V0中的任意頂點(diǎn)yj,yj的所有與葉子相連的邊最多只有一條染了顏色2.因此, 通過交換v的鄰邊中與葉子相鄰邊的顏色, 可達(dá)到邊x2k+1yj都染顏色3的效果, 且點(diǎn)v權(quán)重不發(fā)生變化, 其中0≤k≤(m-1)/2.然后, 將圈Cm上所有的邊都染顏色1.由于點(diǎn)集V0中任一頂點(diǎn)可能的最小度是3, 故滿足σ(yj)≥7, 且xi最大的權(quán)重是5.因此σ(yj)≥σ(xi)總成立.下面根據(jù)兩種情形區(qū)別圈Cm上兩個相鄰頂點(diǎn)xi和xi+1的權(quán)重.

情形1)m≡0(mod 2).將邊x2k+1yj的顏色從3變?yōu)?,x2k+1的權(quán)重變?yōu)?, 且x2k的權(quán)重是4或5.同時,V0中所有頂點(diǎn)的權(quán)重值都會減少2的整數(shù)倍, 因此V0中所有頂點(diǎn)權(quán)重的奇偶性仍未變, 樹T中相鄰頂點(diǎn)的權(quán)重依然是可區(qū)別的.在這種情形下,σ(yj)的最小權(quán)重將會減少到5, 但與yi相鄰的頂點(diǎn)xi的權(quán)重會減少到3或4, 且它們的權(quán)重值總小于σ(yj).在該情形下， 哈林圖的一種鄰和可區(qū)別邊染色如圖1(A)所示.

情形2)m≡1(mod 2).設(shè)圈C上的點(diǎn)x1和xm是v的兩個相鄰點(diǎn), 且v∈V1.類似地, 將邊x2k+1yj的顏色從3變?yōu)?.此時,σ(x2k+1)=3,σ(x2k)=4或5, 但x1和xm的權(quán)重都是3.顯然, 算法1中對樹染色時, 頂點(diǎn)v的鄰邊有一條與葉子相連的鄰邊染了顏色2, 將該邊標(biāo)記為xmv.此時,σ(v)=3dH(v)-1,σ(vi)=3dH(vi) 或3dH(vi)-1,vi∈V(H)V(C).當(dāng)xm-1的權(quán)重是5時, 保持邊xmv的顏色2 不變以保證σ(xm)=4.經(jīng)上述調(diào)色,V0中所有頂點(diǎn)權(quán)重的奇偶性均不變.如果d(v)=3且σ(xm-1)=4, 則將邊xmv的顏色從2變?yōu)?, 將xmxm-1的顏色從1變?yōu)?, 且σ(xm)=4,σ(xm-1)=5.此時,σ(v)的權(quán)重變?yōu)?, 但σ(x1)=3且σ(xm)=4, 所以它們的權(quán)重依然是可區(qū)別的, 且vi的最小權(quán)重為9, 大于σ(v).在該情形下， 哈林圖的一種鄰和可區(qū)別邊染色如圖1(B)所示.證畢.

圖1 兩類哈林圖的鄰和可區(qū)別3-邊染色(伴隨圈上的邊均染顏色1)Fig.1 Neighbor sum distinguishing 3-edge coloring of two types of Halin graphs (edges on adjoint cycle are colored by 1)

3 哈林圖的1-2猜想

算法2

步驟1) 樹T中所有邊染顏色2且所有葉子染顏色1.

步驟2) 選擇點(diǎn)集V1中一個最小度點(diǎn)并標(biāo)記其為v.初始地, 用顏色1染點(diǎn)v.

步驟3) 設(shè)vi是點(diǎn)v的非葉子鄰點(diǎn), 用顏色2染所有的頂點(diǎn)vi.

步驟4) 設(shè)vij是點(diǎn)vi的非葉子鄰點(diǎn), 用顏色1染所有的頂點(diǎn)vij.

步驟5) 重復(fù)步驟2)和步驟3), 直到T中的所有點(diǎn)都染了顏色1或2.

定理2設(shè)H=T∪C為哈林圖, 則tgndi∑(H)≤2.

證明: 首先, 假設(shè)樹T中所有的邊均染了顏色2, 樹T中的各個頂點(diǎn)用顏色1或2染色.則可使用顏色1和2完成對樹T的鄰和可區(qū)別全染色.算法2已證明上述染色是可行的.

由算法2知, 除葉子外, 所有相鄰頂點(diǎn)權(quán)重的奇偶性均不同.V0中所有頂點(diǎn)的可能最小度為3, 且滿足t(xi)=3及t(yj)≥7.圈Cm上所有的邊染顏色1, 可得葉子xi的權(quán)重值都是5.下面通過兩種情形調(diào)整點(diǎn)xi的染色.

情形1)m≡0(mod 2).將點(diǎn)x2k+1的染色從顏色1變?yōu)?, 則x2k+1的權(quán)重即從5變?yōu)?.但點(diǎn)x2k的權(quán)重依然是5.所以t(yj)>t(xi)仍成立.

情形2)m≡1(mod 2).將點(diǎn)x2k+1的顏色從顏色1變?yōu)?, 則x2k+1的權(quán)重從5變?yōu)?.此外, 仍需改變一些點(diǎn)和邊的染色如下:f(xm)=f(xmv)=1,f(v)=2.xm的權(quán)重即為4, 不同于所有鄰點(diǎn)的權(quán)重值, 且v的權(quán)重仍未改變.證畢.

4 哈林圖的NFSD-全染色

算法3

步驟1)T中每個頂點(diǎn)染顏色1.

步驟2) 選擇點(diǎn)集V1中一個最小度點(diǎn)并標(biāo)記其為v.初始地, 對v所有鄰邊都染顏色3.

步驟3) 設(shè)vi是點(diǎn)v的鄰點(diǎn).將點(diǎn)vi的其中一條鄰邊染顏色2, 其余鄰邊都染顏色3.

步驟4) 設(shè)vij是vi的鄰點(diǎn), 對點(diǎn)vij的鄰邊按如下方式染色:

①f(vivij)=2, 將vij的一條未染色鄰邊標(biāo)注顏色2, 剩余的vij所有鄰邊都染顏色3;

②f(vivij)=3,vij的所有鄰邊都染顏色3.

步驟5) 設(shè)vijk是vij的鄰點(diǎn), 按以下方式標(biāo)記點(diǎn)vijk的鄰邊:

①φ(vij)=4dT(vij)+1, 用顏色2染點(diǎn)vijk的一條未染色鄰邊, 點(diǎn)vijk剩余的鄰邊都染顏色3;

②φ(vij)=4dT(vij)-1, 當(dāng)f(vijvijk)=3時, 用顏色2染點(diǎn)vijk的一條未染色鄰邊,vijk剩余的鄰邊都染顏色3, 當(dāng)f(vijvijk)=2時,vijk的所有鄰邊都染顏色3.

步驟6) 重復(fù)步驟4)和步驟5), 直到樹T完成鄰點(diǎn)全和可區(qū)別全染色.

定理3設(shè)H=T∪C為哈林圖, 則fgndi∑(H)≤3.

證明: 首先證明用3種顏色即可完成對樹T的一個鄰點(diǎn)全和可區(qū)別全染色, 染色方案為:T中所有的頂點(diǎn)都染顏色1,T中的邊染顏色2或3.算法3已證明所給染色方案是可行的.

設(shè)Cm=x1x2…xmx1表示伴隨圈.xiyj是邊集E(H)中的邊, 其中xi∈V(Cm),yj∈V0, 1≤i≤m, 1≤j≤|V0|, 且下標(biāo)i和j分別表示對m和|V0|取模.由算法3可知, 相鄰頂點(diǎn)的權(quán)重奇偶性不同.對于V0中的任意頂點(diǎn)v, 其鄰點(diǎn)vxi的鄰邊中最多只有一條邊染顏色2.

情形1)m≡0(mod 2).將邊x2k+1yj的顏色從3變?yōu)?, 所有頂點(diǎn)x2k+1的權(quán)重都是7且x2k的權(quán)重是8或9.同時,V0中所有頂點(diǎn)的權(quán)重減少了2的整數(shù)倍, 因此V0中各頂點(diǎn)權(quán)重的奇偶性不變.在這種情形下,φH(yj)的最小值將減少為9, 但xi或yi鄰點(diǎn)xi的權(quán)重是7或8, 仍然不同于φH(yj).

情形2)m≡1(mod 2).設(shè)x1和xm為圈C上v的兩個相鄰頂點(diǎn)且v∈V1.改變邊x2k+1yj的顏色, 從3變?yōu)?.因此,φ(x2k+1)=7,φ(x2k)=8或9, 但x1和xm的權(quán)重相同, 均為7.顯然,v的所有鄰邊均染顏色3, 且φ(v)=4dH(v)+1,φ(vi)=4dH(vi),vi∈V(H)V(C).當(dāng)xm-1的權(quán)重為8時, 將邊xmv的顏色從顏色1變?yōu)?, 使得φ(xm)=9.經(jīng)過上述染色,V0中所有頂點(diǎn)權(quán)重的奇偶性仍然不變.如果φ(xm-1)=9,d(v)≥4, 將邊xmxm-1的染色從顏色1變?yōu)?, 則φ(xm)=8且φ(xm-1)=10.此時,φ(v)的奇偶性未變.同時,φ(v)≥13總成立.當(dāng)d(v)=3時, 將邊xmv的顏色從1變?yōu)?, 可得φ(xm)=8，φ(v)變?yōu)?0.但當(dāng)vi的度為3時,vi的最小權(quán)重是12.

對任意特征樹T采用算法3以及對伴隨圈上的邊進(jìn)行調(diào)色后, 可得哈林圖鄰點(diǎn)全和可區(qū)別3-全染色.證畢.