關于哈林圖的鄰和可區別染色的注記

程銀萬, 楊 超, 姚 兵

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

1 引言與預備知識

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

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

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

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

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

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

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

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

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

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

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

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

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

算法1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 兩類哈林圖的鄰和可區別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) 選擇點集V1中一個最小度點并標記其為v.初始地, 用顏色1染點v.

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

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

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

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

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

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

情形1)m≡0(mod 2).將點x2k+1的染色從顏色1變為2, 則x2k+1的權重即從5變為6.但點x2k的權重依然是5.所以t(yj)>t(xi)仍成立.

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

4 哈林圖的NFSD-全染色

算法3

步驟1)T中每個頂點染顏色1.

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

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

步驟4) 設vij是vi的鄰點, 對點vij的鄰邊按如下方式染色:

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

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

步驟5) 設vijk是vij的鄰點, 按以下方式標記點vijk的鄰邊:

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

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

步驟6) 重復步驟4)和步驟5), 直到樹T完成鄰點全和可區別全染色.

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

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

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

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

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

對任意特征樹T采用算法3以及對伴隨圈上的邊進行調色后, 可得哈林圖鄰點全和可區別3-全染色.證畢.