圖的（鄰）點可區(qū)別全染色和分數(shù)染色.pdf

1、在本文中，我們用[x]表示不大于實數(shù)x的最大整數(shù)，用[x]表示不小于實數(shù)x的最小整數(shù).用|S|表示集合S中元素的個數(shù). 除非特別指出，本文所討論的圖均為簡單，有限，無向圖.我們用V(G)和E(G)分別表示圖G的頂點集和邊集.對于任意頂點v∈V(G)，用dG(v)表示頂點v在圖G中的度.用δ(G)和△(G)分別表示圖G中頂點的最小度和最大度.G[V′]表示圖G由頂點子集V′導出的子圖，G[E′]表示圖G由邊子集E′導出的子圖.Kn

2、表示n個頂點的完全圖.ω(G)表示圖G的連通分支個數(shù)，κ(G)表示圖G的連通度.α(G)表示圖G的獨立數(shù)，χ(G)表示圖G的色數(shù).本文所用術(shù)語與符號基本與文獻[1]中一致. 隨著圖的染色問題在現(xiàn)實中被廣泛應(yīng)用，它逐漸成為眾多學者研究的重要領(lǐng)域之一.在[2，3]中，起源于網(wǎng)絡(luò)問題的點可區(qū)別邊染色和鄰點可區(qū)別邊染色問題得到進一步研究.新的染色問題不斷被提出，與該問題相關(guān)的，[4，5]中相繼給出了(鄰)點可區(qū)別全染色的定義及其幾類簡單

3、圖關(guān)于此染色的色數(shù)，并提出相關(guān)猜想. 張忠輔給出的(鄰)點可區(qū)別全染色定義是這樣的：設(shè)圖G(V，E)為階至少為2的簡單連通圖，k為正整數(shù).函數(shù)f是從V(G)∪E(G)到C={1，2，…，k}的一個映射. 對于任意頂點u∈V(G)，記C(u)={f(u)}∪{f(uv)|uv∈E(G)}，-C(u)=C-C(u). (1)對任意邊uv，vw∈E(G)，且u≠w，有f(uv)≠f(vw). (2)對任意邊uv

4、∈E(G)，且u≠v，有f(u)≠f(v)，f(u)≠f(uv)，f(uv)≠f(v). (3)對于任意邊uv∈E(G)，且u≠v，有C(u)≠C(v). (4)對于任意點u，v∈V(G)，且u≠v，有C(u)≠C(v). 若滿足條件(1)，(2)，則稱f為圖G的一個k-正常全染色(簡記為k-TC).若滿足條件(1)，(2)，(3)，則稱f為圖G的一個k-鄰點可區(qū)別全染色(簡記為k-AVDTC). 若滿足

5、條件(1)，(2)，(4)，則稱f為圖G的一個k-點可區(qū)別全染色(簡記為k-VDTC). 圖G的全色數(shù)為χT(G)=min{k}圖G有k-TC}.圖G的鄰點可區(qū)別全色數(shù)為χat(G)=min{k|圖G有k-AVDTC}.圖G的點可區(qū)別全色數(shù)為χvt(G)=min{k|圖G有k-VDTC}. 下面兩個關(guān)于鄰點可區(qū)別全染色的結(jié)論顯然：對任意階為n(n=|V(G)|≥2)的簡單連通圖G，鄰點可區(qū)別全色數(shù)χat(G)存在，并且χ

6、at(G)≥△(G)+1.若圖G(V，E)有兩相鄰的最大度頂點，則χat(G)≥△(G)+2.張忠輔在文獻[4]中給出了關(guān)于鄰點可區(qū)別全色數(shù)的猜想：對任意階為n(n=|V(G)|≥2)的簡單連通圖G，有χat(G)≤△(G)+3. 對于路，圈，完全圖，完全二部圖，星，扇，輪，樹等特殊圖類，張忠輔在文獻[4]中給出了具體的鄰點可區(qū)別全色數(shù)，并且滿足上述猜想. 關(guān)于點可區(qū)別全染色，張忠輔在文獻[5]中給出了完全圖，完全二部圖

7、，扇，輪，雙星，還有一系列聯(lián)圖的點可區(qū)別全色數(shù).并提出相關(guān)猜想：對任意階為n(n=|V(G)|≥2)的簡單連通圖G，有KT(G)≤χvt(G)≤KT(G)+1. 其中KT(G)=max{t|t=min{kd|(Ckdd+1)≥nd}，δ(G)≤d≤△(G)}.并且，nd=nd(G)表示圖G中度為d的頂點個數(shù). E.Scheinerman和D.Ullman在[6]中提出了分數(shù)染色的概念，它是圖染色的分數(shù)推廣.作者并指出：確

8、定任意一個圖的分數(shù)色數(shù)是NP-完全問題. 圖G的一個分數(shù)染色是從G的獨立集集合ζ到區(qū)間[0，1]的一個映射C，使得對任意頂點x，都有∑I∈ζ，s,t,x∈IC(I)≥1，將此分數(shù)染色的值定義為∑I∈ζC(I)，圖G的分數(shù)色數(shù)χf(G)是它的所有分數(shù)染色值的下確界. 圖G的分數(shù)色數(shù)另一個等價定義為χf(G)=limb→∞χb(G)b=infbχb(G)/b，其中χb(G)為G的b-層色數(shù).給圖G的每個頂點以一個b種顏色的色

9、集，使得相鄰兩頂點的色集不交，若所有顏色均取自一個a種顏色的色集，這時，我們稱圖G是a：b-可染的，且稱此染色為一個a：b-染色.使得圖G有一個a：b-染色的最小的a，稱為圖G的b-層色數(shù).即χb(G)=min{a|G有一個a：b-染色}. 在本文中，關(guān)于圖的(鄰)點可區(qū)別全染色，我們主要得到如下定理.具有頂點集V(G)={ui∪vj|i=1，2，…，m；j=1，2，…，n；m≥n≥2}和邊集E(G)={uivj|i=1，…，m

10、；1≤j≤i}的圖，我們稱之為“次完全二部圖”.記作：Gm,n*. 定理2.1.1χat(Gm,n*)={m+2,m=n≥2m+1,m＞n≥2.在圈CN=v1v2…unv1的每個頂點vi上增加一條懸掛邊vivi1(i=1，…，n)，得到圖Yn(1)，在每個頂點vi上再增加一條懸掛邊vivi2(i=1，…，n)，得到圖Yn(2)，…，第k次(k可任意大)增加懸掛邊vivik(i=1，…，n)，得到圖Yn(k)…這樣，我們得到一系列

11、的煙花圖Yn(1)，Yn(2)，…，Yn(k)…..其中圖Yn(1)，為我們所熟知的王冠Qn. 定理2.1.2χat(Yn(k))=k+4(n≥3). 定理2.1.3χvt(Yn(1))=χvt(Qn)=n(n≥5). 在兩圈C1=u1u2…unu1(n≥3)和C2=v1v2…vnv1(n≥3)間逐次疊加匹配uivi，uivi+1，…，uivi+k，…，uivi+(n-1)，(i=1，2，…，n；k=0，1，…，

12、n-1；當i+k＞n+1時，i+k為modn意義下的加法)，這樣可得到一系列正則圖：Cn,n(1)，Cn,n(2)，…，Cn,n(k+1)，…，Cn,n(n)=Cn∨Cn. 定理2.1.4當n≥4且n≡0(mod2)時，χat(Cn,n(k+1))=△(Cn,n(k+1))+2=k+5. 定理2.1.5當n≥4且n≡1(mod2)時，(1)χat(Cn,n(1))=5. (2)當1≤k≤n-1時，k+5≤χat(

13、Cn,n(k+1))≤k+6.在王冠Qn(n≥3)的懸掛點ui上加邊uivi-1和utivi+1(i=2，3，…，n-1)；在點u1上加邊u1v2和u1vn；在點un上加邊unvn-1和unv1；得到特殊王冠Qn*. 定理2.1.6χat(Qn*)=7(n≥3). 將圈Cn=v1v2…vnv1(n≥3)的每條邊vivi+1(i=n時，為vnv1)以雙重邊(無方向)代替，對每對雙重邊外部的一條相應(yīng)的加剖分點vi(i=1，2

14、，…，n)，得到向日葵Hn. 定理2.1.7χat(Hn)=6(n≥3). 在向日葵Hn(n≥3)的邊vivi+1(i=n時，為vnv1)上相應(yīng)的加剖分點wi(i=1，2，…，n)，得到籬笆圈Pn*. 定理2.1.8χT(Pn*)=χat(Pn*)=5(n≥3).在圈C2n=v1v2…v2n-1v2nv1(n≥2)的每個頂點vi上增加懸掛邊viui(i=1，2，…，2n)，再加邊uiui+1(i≡1(mod2))

15、，得到風車W2n*. 定理2.1.9χat(W2n*)=5(n≥2).在本文中，關(guān)于圖的分數(shù)染色，我們主要得到如下結(jié)果：給定正整數(shù)a，b，且a≥2b，圖Ga,b是如下定義的[6]:其頂點集V(Ga,b)={v0，v1，…，va-1}；頂點vi的鄰點為{vi+b，vi+b+1，…，vi+a+b}，其中加法是moda的. 圖G稱為頂點可遷圖[6]：對任意頂點u，v∈V(G)，存在G的自同構(gòu)射π，使得π(u)=v. 性

16、質(zhì)2.2.1[6]χf(Ga，b)=a/b；χb(Ga,b)=a. 性質(zhì)2.2.2[6]對任意圖G，有χf(G)≥v(G)/a(G)；進一步，當G是頂點可遷圖時，等號成立. 引理2.2.3對任意頂點v∈V(Ga,b)，有a-1/b≤χf(Ga,b-v)≤a/b. 定理2.2.4當a=kb時，k∈Z且k≥2，有χf(Ga,b-v)=a/b. 定理2.2.5當a=2b+1時，χf(Ga，b-v)=a-1/b.

17、 在圖Ga，b中，令ei=(vi，vi+b)，i=0，1，…，a-1.加法是moda的. 定理2.2.6當e≠ei時，χf(Ga，b-e)=a/b. 引理2.2.7a-1/b≤χf(Ga,b-ei)≤a/b，i=0，1，…，a-1. 定理2.2.8當a=kb時，k∈Z且k≥2，有χf(Ga，b-ei)=a/b，i=0，1，…，a-1. 定理2.2.9當a=2b+1時，χf(Ga，b-ei)=a-1