樹的D(r)-點(diǎn)可區(qū)別邊染色

李澤鵬， 耿培倫, 陳祥恩

(1.蘭州大學(xué) 信息科學(xué)與工程學(xué)院， 甘肅 蘭州 730000; 2.西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 甘肅 蘭州 730070)

0 引 言

圖的可區(qū)別染色是近年來圖染色研究的熱點(diǎn)問題，主要體現(xiàn)圖的局部結(jié)構(gòu)顏色集合之間的可區(qū)別性.圖的點(diǎn)可區(qū)別正常邊染色是Burris在其博士論文中首次提出的[1]，此后該問題也被稱為強(qiáng)邊染色[2].圖G的點(diǎn)可區(qū)別正常邊染色是指G的一個正常邊染色，使得任意兩個頂點(diǎn)的色集合不同.使得G有k-點(diǎn)可區(qū)別正常邊染色的最小正整數(shù)k稱為G的點(diǎn)可區(qū)別正常邊色數(shù)，記為′v(G).

Zhang等[3]將任意兩點(diǎn)可區(qū)別的條件放松為任意兩個相鄰頂點(diǎn)可區(qū)別，從而提出了鄰點(diǎn)可區(qū)別正常邊染色的概念(也稱為鄰強(qiáng)邊染色).圖G的鄰點(diǎn)可區(qū)別邊色數(shù)是指對G進(jìn)行鄰點(diǎn)可區(qū)別邊染色所需要的最小色數(shù)，記為′a(G).通過分析一些特殊圖類，如樹、圈、完全二部圖和完全圖等的鄰點(diǎn)可區(qū)別正常邊色數(shù)，學(xué)者們提出了下面的猜想.

猜想1對任意連通圖G(|V(G)|≥6), 有

′a(G)≤Δ(G)+2.

對于更一般的情況，張忠輔等[4]在2006年提出了圖的距離不大于r的任意兩點(diǎn)可區(qū)別的正常邊染色，即D(r)-點(diǎn)可區(qū)別正常邊染色.顯然，當(dāng)r=1時，圖G的D(r)-點(diǎn)可區(qū)別正常邊染色，即G的鄰點(diǎn)可區(qū)別正常邊染色；當(dāng)r≥d(G)時，圖G的D(r)-點(diǎn)可區(qū)別正常邊染色，即G的點(diǎn)可區(qū)別正常邊染色，其中，d(G)是圖G的直徑.并且，對任意正整數(shù)r，有：

引理1設(shè)G是階數(shù)至少為3的連通圖，則

′a(G)≤′r(G)≤′v(G).

特別地，文獻(xiàn)[4]得到了一些特殊圖類，如圈、扇、輪、完全圖、完全二部圖、樹以及一些聯(lián)圖的D(2)-點(diǎn)可區(qū)別邊色數(shù)，并提出了如下猜想：

猜想2當(dāng)r≥2時，對任意圖G有

μr(G)≤′r(G)≤μr(G)+1，

注意，圖的D(r)-點(diǎn)可區(qū)別邊染色也稱為r-強(qiáng)邊染色，此概念是Akbari等[5]獨(dú)立提出的.

然而，猜想2被Kemnitz等[6]于2014年否定了.他們發(fā)現(xiàn)了一類圈Cp，滿足D(2)-點(diǎn)可區(qū)別邊色數(shù)′2(Cp)=μ2(Cp)+2，其中，

雖然猜想2被否定了，但是確定圖的D(r)-點(diǎn)可區(qū)別邊色數(shù)上界的問題仍是很有意義的工作.Tian等[8]利用概率方法得到了圖的D(r)-點(diǎn)可區(qū)別邊色數(shù)一個上界.

猜想3對任意正整數(shù)r≥2，存在常數(shù)δ0和C，使得對任意不含孤立邊且最小度δ(G)≥δ0的圖G，有

′r(G)≤Δ(G)+C.

劉利群等[10]確定了路與圈的Mycielski圖的D(2)-點(diǎn)可區(qū)別邊色數(shù).關(guān)于圖的D(r)-點(diǎn)可區(qū)別邊染色詳細(xì)的研究參見文獻(xiàn)[11].

關(guān)于樹的D(r)-點(diǎn)可區(qū)別邊染色，Akbari等[5]證明了：對任意樹T, 有′2(T)≤Δ(T)+1，且當(dāng)T的任意兩個最大度頂點(diǎn)之間的距離大于等于3時，′2(T)=Δ(T)；對最大度Δ(T)≥3的樹T, 有′3(T)≤2Δ(T)-1.

1 預(yù)備知識

本文所涉及的圖均為簡單無向圖.設(shè)G=(V(G),E(G))是一個圖，其中V(G)和E(G)分別表示G的頂點(diǎn)集和邊集.對頂點(diǎn)v∈V(G)，用d(v)表示v在G中的度數(shù)，N(v)表示v的所有鄰點(diǎn)構(gòu)成的集合.由于G是簡單圖，故d(v)=|N(v)|.若d(v)=1，則稱v為G的葉子.用N1(v)表示v的鄰點(diǎn)中所有葉子構(gòu)成的集合.圖G的最大度和最小度分別記為Δ(G)和δ(G).對頂點(diǎn)u,v∈V(G)，用d(u,v)表示u和v之間的距離，即u到v最短路的長度.圖G的直徑是指G中兩個頂點(diǎn)之間的最大距離，記為diam(G)，即

diam(G)=max{d(u,v):u,v∈V(G)}.

圖G的一個正常邊染色是指對G的每條邊分配一種顏色,使得任意相鄰的兩條邊的顏色不同.設(shè)f是圖G的一個正常邊染色，v∈V(G)，記

C′(v)={f(vw):vw∈E(G)}，

稱C′(v)為頂點(diǎn)v在邊染色f下的色集合.

定義1[4]設(shè)f:V(G)→{1,2,…,k}是圖G的一個正常邊染色，如果對G中任意兩個距離不超過r的頂點(diǎn)u,v∈V(G)，有C′(u)≠C′(v)，則稱f為G的D(r)-點(diǎn)可區(qū)別邊染色.圖G的D(r)-點(diǎn)可區(qū)別邊色數(shù)是指對圖G進(jìn)行D(r)-點(diǎn)可區(qū)別邊染色所需要的最小色數(shù)，記為′r(G)，即

′r(G)=min{k:G有D(r)-點(diǎn)可區(qū)別邊染色}.

圖G的一個正常全染色f是指對G的每個頂點(diǎn)以及每條邊分配一種顏色使得：

(1)對任意uv,vw∈E(G)，u≠w，有f(uv)≠f(vw);

(2)對任意uv∈E(G)，有f(u)≠f(v)，f(u)≠f(uv)，f(v)≠f(uv).

設(shè)f是G的一個正常全染色，v∈V(G)，記

C″(v)={f(v)}∪{f(vw):vw∈E(G)}，

稱C″(v)為頂點(diǎn)v在全染色f下的色集合.

定義2[12-13]設(shè)f:V(G)∪E(G)→{1,2,…,k}是圖G的一個正常全染色，如果對G中任意兩個距離不超過r的頂點(diǎn)u,v∈V(G)，有C″(u)≠C″(v)，則稱f為G的D(r)-點(diǎn)可區(qū)別全染色.圖G的D(r)-點(diǎn)可區(qū)別全色數(shù)是指對圖G進(jìn)行D(r)-點(diǎn)可區(qū)別全染色所需要的最小色數(shù)，記為″r(G)，即″r(G)=min{k:G有D(r)-點(diǎn)可區(qū)別全染色}.

類似于鄰點(diǎn)可區(qū)別邊染色的概念，當(dāng)r=1時，圖G的D(r)-點(diǎn)可區(qū)別正常全染色即為G的鄰點(diǎn)可區(qū)別正常全染色[14]，此問題已被廣泛研究.

文中未給出的定義及符號，請參照圖論文獻(xiàn)[11,15].

2 樹的D(r)-點(diǎn)可區(qū)別邊染色

本節(jié)討論樹T的D(2)-點(diǎn)可區(qū)別邊染色和D(3)-點(diǎn)可區(qū)別邊染色，分別得到了對應(yīng)的邊染色的上界，并給出了線性時間的染色方案.

2.1 樹的D(2)-點(diǎn)可區(qū)別邊染色

Akbari等[5]證明了對任意樹T有′2(T)≤Δ(T)+1成立，本小節(jié)給出了一種簡單的證明方法.

定理1對任意樹T，可在線性時間給出T的一個使用了不超過Δ(T)+1種顏色的D(2)-點(diǎn)可區(qū)別邊染色.

證明設(shè)總顏色集C={1,2,…,Δ(T)+1}，T的根節(jié)點(diǎn)為u.下面從樹T的根u出發(fā)，逐層對T的邊進(jìn)行染色，并滿足所有關(guān)聯(lián)的邊已染色的點(diǎn)是D(2)-點(diǎn)可區(qū)別的.

由于總顏色數(shù)為Δ(T)+1，因此,在染色之后每個頂點(diǎn)x的色集合C′(x)中至少有一種顏色沒有出現(xiàn).在下面染色中，筆者總是假定c(x)是C′(x)中未出現(xiàn)的一種顏色.

染色方案f如下：

對根節(jié)點(diǎn)u，令C′(u)={1,2,…,d(u)}，取c(u1),c(u2),…,c(ud(u))分別為f(uu2)、f(uu3)、…、f(uud(u))和f(uu1)，其中，u1,u2,…,ud(u)是u的子節(jié)點(diǎn).

對其他任意節(jié)點(diǎn)x，設(shè)x的父節(jié)點(diǎn)為y，y的父節(jié)點(diǎn)為z(若存在)，且x是y的第m個子節(jié)點(diǎn).令f(xx1)=c(y)，c(x)=f(yym+1)(當(dāng)y≠u且m=d(y)-1時，c(x)=f(yz))，并令f(xx2),f(xx3), …,f(xxd(x)-1)為在C{c(x),f(xy),f(xx1)}中從大于f(xy)的第一個數(shù)開始順序循環(huán)所取的d(x)-2種顏色.由于總顏色數(shù)為Δ(T)+1，所以|C{c(x),f(xy),f(xx1)}|≥d(x)-2.

易驗(yàn)證上述染色過程是線性時間的.下面證明此染色方案f是T的D(2)-點(diǎn)可區(qū)別邊染色.因?yàn)橹挥卸认嗤捻旤c(diǎn)才可能有相同的色集，故下面討論的頂點(diǎn)度均相等，且只討論層數(shù)不低于x的節(jié)點(diǎn)，低于x的節(jié)點(diǎn)同理.

當(dāng)x是T的葉子時，與x距離不超過2且是葉子的節(jié)點(diǎn)一定是y的鄰點(diǎn)，根據(jù)上述染色規(guī)則可知，它們與x的顏色集不同，即與x是可區(qū)別的.下面考慮x不是T的葉子的情況.

(1) 與x距離為2的頂點(diǎn)包括z及y的除x外的子節(jié)點(diǎn).

因?yàn)閏(x)=f(yym+1)≠f(yy1)=c(z)，所以x與z的色集合不同.對y的除x外的任意子節(jié)點(diǎn)yt，因?yàn)閏(x)≠c(yt)，且f(xy)≠f(yyt)，結(jié)合每個節(jié)點(diǎn)關(guān)聯(lián)邊上順序染色的規(guī)則可知C′(x)≠C′(yt).

(2) 與x距離為1的頂點(diǎn)只有y.因?yàn)閒(xx1)=c(y)，即C′(x)包含C′(y)缺少的顏色，故x與y的色集合是不同的.

□

2.2 樹的D(3)-點(diǎn)可區(qū)別邊染色

當(dāng)T是星或雙星時，即T中至多有兩個頂點(diǎn)度數(shù)大于等于2，其余頂點(diǎn)的度數(shù)都是1時，diam(T)≤3，即T中任意兩個頂點(diǎn)之間的距離都不超過3，因此，′3(T)=|E(T)|.

設(shè)T是一棵根為t的樹，v是T中的任一頂點(diǎn).用d1(v)表示v的鄰點(diǎn)中葉子的數(shù)目.

定理2設(shè)T是一棵根為t的樹，diam(T) ≥4，且t是T的葉子.令

h=max{d1(x)+d1(y)+2|x,y∈V(G)}，

則T存在使用了不超過max{Δ(T)+2,h}種顏色的D(3)-點(diǎn)可區(qū)別邊染色.

證明設(shè)k=max{Δ(T)+2,h}，且使用的總顏色集C={1,2,…,k}.下面從樹T的根t出發(fā)，逐層對T的邊進(jìn)行染色，并滿足所有關(guān)聯(lián)的邊已染色的點(diǎn)是D(3)-點(diǎn)可區(qū)別的.

由于k=max{Δ(T)+2,h}≥Δ(T)+2，因此,在染色之后每個頂點(diǎn)x的色集合C′(x)中至少有兩種顏色沒有出現(xiàn).在下面染色中，筆者總是假定c1(x)和c2(x)是C′(x)中未出現(xiàn)的兩種顏色.

染色方案f如下：

(1)對根頂點(diǎn)t，設(shè)其唯一鄰點(diǎn)為u,并令f(tu)=1. 取c1(t)=d(u)，c2(t)=d(u)+1.

(2)設(shè)u的孩子節(jié)點(diǎn)分別為u1,u2,…,ud(u)-1，令f(uui)=i+1，i=1,2,…,d(u)-1(圖1). 并且，令c1(u)=d(u)+1，c2(u)=d(u)+2.

圖1 頂點(diǎn)u的關(guān)聯(lián)邊的染色方案Fig.1 The coloring of the incident edges of u

(3)從u的孩子節(jié)點(diǎn)開始，逐層對u的子孫節(jié)點(diǎn)關(guān)聯(lián)的未染色邊進(jìn)行染色.

對任意頂點(diǎn)x，設(shè)x的父節(jié)點(diǎn)為y，y的父節(jié)點(diǎn)為z，且x是y的第m個孩子，x的子節(jié)點(diǎn)分別為x1,x2,…xd(x)-1. 假設(shè)T中頂點(diǎn)y所在層及以上的頂點(diǎn)所關(guān)聯(lián)的邊均已經(jīng)染好顏色，如圖2所示.下面對頂點(diǎn)x關(guān)聯(lián)的未染色邊進(jìn)行染色.用S(y)表示頂點(diǎn)y的關(guān)聯(lián)邊中一個端點(diǎn)是葉子的邊的顏色集合，即S(y)={f(yw):w∈N1(y)}.顯然，S(y)中的顏色在x關(guān)聯(lián)的懸掛邊上是不能出現(xiàn)的.

圖2 樹T的結(jié)構(gòu)和染色Fig.2 The structure and coloring of the tree T

若x的子節(jié)點(diǎn)都是葉子且d1(y)+d1(x)=k-2，則c1(x),c2(x)待定.若y=u,y的子節(jié)點(diǎn)中除x外都是葉子，且d1(y)+d1(x)=k-2, 則c1(x),c2(x)待定.

對其余情況，都令c1(x)=c2(y)，c2(x)=f(yym+1)，當(dāng)x=yd(y)-1時，令c2(x)=f(zy).

以下對與x關(guān)聯(lián)的未染色邊進(jìn)行染色.

R1 若x的子節(jié)點(diǎn)中或y的子節(jié)點(diǎn)中沒有葉子，則令{f(xx1)}={c1(z),c2(z)}∩{c1(y),c2(y)}，f(xx2),f(xx3),…,f(xxd(x)-1)分別為在C{c1(x),c2(x)}中從大于f(xy)的數(shù)開始順序取d(x)-2個顏色，若顏色取盡則回到集合中的第一個顏色.

R2 若x和y的子節(jié)點(diǎn)中都存在葉子，但x的子節(jié)點(diǎn)不都是葉子或d1(y)+d1(x)

R3 若x和y的子節(jié)點(diǎn)中都存在葉子，x的子節(jié)點(diǎn)都是葉子且d1(y)+d1(x)=k-2，則f(xx1),f(xx2),…,f(xxd(x)-1)分別為在CS(y)中從大于f(xy)的數(shù)開始順序取d(x)-1個顏色.

下面證明此染色方案f是T的D(3)-點(diǎn)可區(qū)別邊染色.因?yàn)橹挥卸认嗤捻旤c(diǎn)才可能擁有相同的色集，故下面討論的頂點(diǎn)度均相等，且只討論層數(shù)不低于x的頂點(diǎn)，低于x的頂點(diǎn)同理.設(shè)z的父節(jié)點(diǎn)為w(若存在).

若x的子節(jié)點(diǎn)都是葉子，或者y=u且y的子節(jié)點(diǎn)中除x外都是葉子，且d1(y)+d1(x)=k-2，則f(xy)=c1(z)=c2(w)，故x與z和w一定可區(qū)別.另外，對z的任意子節(jié)點(diǎn)zi，由于c1(y)=c1(zi)=c2(z)，但由染色規(guī)則R3可知，C′(x)包含顏色c1(y)，故x與zi是可區(qū)別的.

若x是T的葉子，則與x距離不超過3且是葉子的節(jié)點(diǎn)一定是y或z的鄰點(diǎn)，根據(jù)染色規(guī)則R2和R3可知，它們與x的顏色集不同，即與x是可區(qū)別的.下面考慮x不是T的葉子的情況.

(1)與x距離為3的頂點(diǎn)包括w及z的除y外的子節(jié)點(diǎn).

由上述染色規(guī)則可知，c2(w)=c1(z)=f(yy1), 因此，c2(w)?{c1(x),c2(x)}，此時，若f(xy)≠f(wp)，其中p是w的父節(jié)點(diǎn)，則根據(jù)每個節(jié)點(diǎn)關(guān)聯(lián)邊上順序染色的規(guī)則可知,C′(x)≠C′(w)；若f(xy)=f(wp)，則根據(jù)c1(x),c2(x)的選取可知，c2(x)=f(yym+1)，但節(jié)點(diǎn)w關(guān)聯(lián)邊上是順序染色的，因此，也有C′(x)≠C′(w).

設(shè)zi是z的除y外的任意子節(jié)點(diǎn).由染色規(guī)則R1可知f(xx1)=c1(y)=c2(z)，而c1(zi)=c2(z)，因此，f(xx1)=c1(zi). 這說明f(xx1)∈C′(x)，但f(xx1)?C(zi). 所以，C′(x)≠C′(zi).

(2)與x距離為2的頂點(diǎn)包括z及y的除x外的子節(jié)點(diǎn).由染色規(guī)則R1可知f(xx1)=c2(z)，即有f(xx1)∈C′(x)，但f(xx1)?C′(z)， 所以C′(x)≠C′(z).

對y的除x外的任意子節(jié)點(diǎn)yt，因?yàn)閏2(x)≠c2(yt)，且f(xy)≠f(yyt)，結(jié)合每個節(jié)點(diǎn)關(guān)聯(lián)邊上順序染色的規(guī)則可知C′(x)≠C′(yt).

(3)與x距離為1的頂點(diǎn)只有y.因?yàn)閏2(x)=c1(y)，c1(x)≠c2(y)，且f(xy)≠f(yz)，所以C′(x)≠C′(y).

綜上可知，f是T的D(3)-點(diǎn)可區(qū)別邊染色，即有′3(T)≤max{Δ(T)+2,h}.

□

由定理2的證明過程可知下面結(jié)論成立.

推論1對任意樹T，diam(T)≥4，可在線性時間給出T的使用不超過max{Δ(T)+2,h}種顏色的D(3)-點(diǎn)可區(qū)別邊染色.

推論2設(shè)T是一棵樹，diam(T)≥4，且h=max{d1(x)+d1(y)+2|x,y∈V(G)}≤Δ(T)+2, 則′3(T)≤Δ(T)+2.

3 樹的D(r)-點(diǎn)可區(qū)別全染色

本節(jié)在樹的D(2)-和D(3)-點(diǎn)可區(qū)別邊染色基礎(chǔ)上，進(jìn)一步討論樹的D(2)-和D(3)-點(diǎn)可區(qū)別全染色.

定理3對任意樹T，可在線性時間給出T的一個使用了不超過Δ(T)+3種顏色的D(2)-點(diǎn)可區(qū)別全染色.

證明對T中的邊采用定理3中的染色方案對其進(jìn)行染色，可得到T的一個使用了不超過Δ(T)+1種顏色的D(2)-點(diǎn)可區(qū)別邊染色.然后對T的頂點(diǎn)用兩種新顏色進(jìn)行正常點(diǎn)染色，則所得到的染色f是T的D(2)-點(diǎn)可區(qū)別全染色.

□

事實(shí)上，通過定理3的證明過程得到的染色f也是T的D(3)-點(diǎn)可區(qū)別全染色.因?yàn)門中任意兩個距離為3的頂點(diǎn)的點(diǎn)顏色是不同的，故它們的色集合也是不同的.所以，定理4成立.

定理4對任意樹T，可在線性時間給出T的一個使用了不超過Δ(T)+3種顏色的D(3)-點(diǎn)可區(qū)別全染色.

□

另外，可通過定理2來證明定理4，具體證明過程如下：

對任意給定的樹T，不妨設(shè)其頂點(diǎn)數(shù)大于等于3，給T的每個頂點(diǎn)上增加一條新的懸掛邊，所得到的圖仍是一棵樹，記為T*. 即有：

V(T*)=V(T)∪{v*:?v∈V(T)},

E(T*)=E(T)∪{vv*:?v∈V(T)}.

顯然，有Δ(T*)=Δ(T)+1，且

max{d1(x)+d1(y)+2|x,y∈V(T*)}=

2<Δ(T*)+2,

利用定理2的證明過程和推論2可知，在線性時間可得到T*的一個使用了不超過Δ(T*)+2種顏色的D(3)-點(diǎn)可區(qū)別邊染色f*.下面在f*的基礎(chǔ)上定義T的全染色f如下：

(1)對任意頂點(diǎn)v∈V(T)，令f(v)=f*(vv*)；

(2)對任意邊uv∈E(T)，令f(uv)=f*(uv)；

由于f*是T*的D(3)-點(diǎn)可區(qū)別邊染色，因此,對T中任意兩個相鄰的頂點(diǎn)u和v，邊uu*和vv*在f*下的顏色是不同的，由f的定義可知，f(u)≠f(v),所以，f是T的一個正常全染色.另外，根據(jù)f與f*的關(guān)系可知，對T中任意頂點(diǎn)x，有C″(x)=C′(x)，所以f是T的D(3)-點(diǎn)可區(qū)別全染色.

□

下面，對定理3的結(jié)論進(jìn)行改進(jìn)，可得到樹T的一個使用了不超過Δ(T)+2種顏色的D(2)-點(diǎn)可區(qū)別全染色.

定理5設(shè)T是一棵樹，則

″2(T)≤Δ(T)+2.

證明當(dāng)Δ(T)≤2時，易驗(yàn)證″2(T)≤4.

下面考慮Δ(T)≥3的情況.設(shè)使用的總顏色集C={1,2,…,Δ(T)+2}，樹T的根節(jié)點(diǎn)是u，且d(u)=Δ(T). 下面從樹T的根u出發(fā)，逐層對T的點(diǎn)和邊進(jìn)行染色，并滿足所有關(guān)聯(lián)的邊和點(diǎn)本身已染色的頂點(diǎn)是D(2)-點(diǎn)可區(qū)別的.

由于總顏色數(shù)為Δ(T)+2，因此,在染色之后每個頂點(diǎn)x的色集合Cii(x)中至少有一種顏色沒有出現(xiàn).在以下染色中，筆者總是假定c(x)是Cii(x)中未出現(xiàn)的顏色.

染色方案f如下：

對根節(jié)點(diǎn)u，令C″(u)={1,2,…,d(u)}，f(u)=d(u)+1,取c(u1),c(u2),…,c(ud(u))分別為f(uu2),f(uu3),…,f(uud(u)),f(uu1)，其中,u1,u2, …,ud(u)是u的子節(jié)點(diǎn).

對其他任意節(jié)點(diǎn)x，設(shè)x的父節(jié)點(diǎn)為y，y的父節(jié)點(diǎn)為z，x的子節(jié)點(diǎn)分別為x1,x2,…xd(x)-1，并且x是y的第m個子節(jié)點(diǎn).

如果x是T的葉子，則只對頂點(diǎn)x進(jìn)行染色即可.此時，令f(x)=c(y).

如果x不是T的葉子，則：

(1)令f(xx1)=c(y)，c(x)=f(yym+1)(當(dāng)x≠ud(u)且m=d(y)-1時，令c(x)=f(yz))；

(2)取f(x)∈C{f(y),f(xy),f(xx1),c(x)}；

(3)令f(xx2),f(xx3),…,f(xxd(x)-1)為在C{c(x),f(x),f(xy),f(xx1)}中從大于f(xy)的第一個數(shù)開始順序循環(huán)所取的d(x)-2種顏色，如圖3所示(圖中[p]表示該頂點(diǎn)缺少的顏色為p).

圖3 一棵最大度為3的樹的D(2)-點(diǎn)可區(qū)別全染色

由于|C{c(x),f(x),f(xy),f(xx1)}|≥Δ(T)+2 -4≥d(x)-2，故上述染色方案(3)是有效的.

下面證明此染色方案f是T的D(2)-點(diǎn)可區(qū)別全染色.只證明任意頂點(diǎn)x與其祖先頂點(diǎn)是可區(qū)別的.

當(dāng)x是T的葉子時，與x距離不超過2且是葉子的節(jié)點(diǎn)一定是y的鄰點(diǎn)，根據(jù)上述染色規(guī)則可知，y的所有關(guān)聯(lián)邊的顏色是不同的，但y的所有葉子鄰點(diǎn)的顏色都是c(y)，因此,x與y的其他葉子鄰點(diǎn)的色集合是不同的.下面考慮x不是T的葉子的情況.

(1)與x距離為2的頂點(diǎn)包括z及y的除x外的子節(jié)點(diǎn).

因?yàn)閒(xy)=c(z)，即C″(x)包含C″(z)缺少的顏色，所以x與z的色集合是不同的.對y的除x外的任意子節(jié)點(diǎn)yt，因?yàn)閏(x)≠c(yt)，且f(xy)≠f(yyt)，所以，結(jié)合每個節(jié)點(diǎn)關(guān)聯(lián)邊上順序染色的規(guī)則可知，C″(x)≠C″(yt).

(2)與x距離為1的頂點(diǎn)只有y.因?yàn)閒(xx1)=c(y)，即C″(x)包含C″(y)缺少的顏色，故x與y的色集合是不同的.

綜上所述，f是T的D(2)-點(diǎn)可區(qū)別全染色，因此，″2(T)≤Δ(T)+2.

□

4 結(jié) 論

本文對樹的D(2)-點(diǎn)可區(qū)別邊(全)染色和D(3)-點(diǎn)可區(qū)別邊(全)染色進(jìn)行了討論，分別得到染色數(shù)的上界，并給出了線性時間的染色方案.

樹的D(r)-點(diǎn)可區(qū)別邊色數(shù)主要受到距離不超過r的葉子頂點(diǎn)數(shù)目的影響.特別地，當(dāng)r比較大時，影響更為明顯.

對任意k≥4，Akbari等[5]構(gòu)造了樹T，滿足

′k-vd(T)≥Δ(T)(Δ(T)-1)|k/2|-1，

其構(gòu)造如下：令u是T的根，讓T中與u的距離小于|k/2|的頂點(diǎn)的度數(shù)均為Δ(T)，與u的距離等于|k/2|的頂點(diǎn)的度數(shù)均為1. 可以看出，T中包含Δ(T)(Δ(T)-1)|k/2|-1個度為1的頂點(diǎn)，且任意兩個的距離不超過k，因此，′k-vd(T)≥Δ(T)(Δ(T)-1)|k/2|-1.

但樹的D(r)-點(diǎn)可區(qū)別全色數(shù)受到距離不超過r的葉子頂點(diǎn)數(shù)目的影響較小，因?yàn)樵谌旧旅總€頂點(diǎn)都有顏色，從而增加了備選的色集合.

對圖G, 令

其中，ni表示度為i且任意兩點(diǎn)間的距離不超過β的頂點(diǎn)的最大數(shù)目.

易驗(yàn)證，ηr(G)是圖G具有D(r)-點(diǎn)可區(qū)別全染色所需顏色數(shù)的一個下界，即″r(G)≥ηr(G).

張忠輔等[12-13]猜想對任意圖G有

ηr(G)≤′r(G)≤ηr(G)+1，