圖的（鄰）點(diǎn)可區(qū)別全染色和分?jǐn)?shù)染色.pdf

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

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

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

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

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

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

7、，扇，輪，雙星，還有一系列聯(lián)圖的點(diǎn)可區(qū)別全色數(shù).并提出相關(guān)猜想：對(duì)任意階為n(n=|V(G)|≥2)的簡(jiǎn)單連通圖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的頂點(diǎn)個(gè)數(shù). E.Scheinerman和D.Ullman在[6]中提出了分?jǐn)?shù)染色的概念，它是圖染色的分?jǐn)?shù)推廣.作者并指出：確

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

9、集，使得相鄰兩頂點(diǎn)的色集不交，若所有顏色均取自一個(gè)a種顏色的色集，這時(shí)，我們稱圖G是a：b-可染的，且稱此染色為一個(gè)a：b-染色.使得圖G有一個(gè)a：b-染色的最小的a，稱為圖G的b-層色數(shù).即χb(G)=min{a|G有一個(gè)a：b-染色}. 在本文中，關(guān)于圖的(鄰)點(diǎn)可區(qū)別全染色，我們主要得到如下定理.具有頂點(diǎn)集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的每個(gè)頂點(diǎn)vi上增加一條懸掛邊vivi1(i=1，…，n)，得到圖Yn(1)，在每個(gè)頂點(diǎn)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；當(dāng)i+k＞n+1時(shí)，i+k為modn意義下的加法)，這樣可得到一系列正則圖：Cn,n(1)，Cn,n(2)，…，Cn,n(k+1)，…，Cn,n(n)=Cn∨Cn. 定理2.1.4當(dāng)n≥4且n≡0(mod2)時(shí)，χat(Cn,n(k+1))=△(Cn,n(k+1))+2=k+5. 定理2.1.5當(dāng)n≥4且n≡1(mod2)時(shí)，(1)χat(Cn,n(1))=5. (2)當(dāng)1≤k≤n-1時(shí)，k+5≤χat(

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

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

15、，得到風(fēng)車(chē)W2n*. 定理2.1.9χat(W2n*)=5(n≥2).在本文中，關(guān)于圖的分?jǐn)?shù)染色，我們主要得到如下結(jié)果：給定正整數(shù)a，b，且a≥2b，圖Ga,b是如下定義的[6]:其頂點(diǎn)集V(Ga,b)={v0，v1，…，va-1}；頂點(diǎn)vi的鄰點(diǎn)為{vi+b，vi+b+1，…，vi+a+b}，其中加法是moda的. 圖G稱為頂點(diǎn)可遷圖[6]：對(duì)任意頂點(diǎn)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]對(duì)任意圖G，有χf(G)≥v(G)/a(G)；進(jìn)一步，當(dāng)G是頂點(diǎn)可遷圖時(shí)，等號(hào)成立. 引理2.2.3對(duì)任意頂點(diǎn)v∈V(Ga,b)，有a-1/b≤χf(Ga,b-v)≤a/b. 定理2.2.4當(dāng)a=kb時(shí)，k∈Z且k≥2，有χf(Ga,b-v)=a/b. 定理2.2.5當(dāng)a=2b+1時(shí)，χf(Ga，b-v)=a-1/b.

17、 在圖Ga，b中，令ei=(vi，vi+b)，i=0，1，…，a-1.加法是moda的. 定理2.2.6當(dāng)e≠ei時(shí)，χ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當(dāng)a=kb時(shí)，k∈Z且k≥2，有χf(Ga，b-ei)=a/b，i=0，1，…，a-1. 定理2.2.9當(dāng)a=2b+1時(shí)，χf(Ga，b-ei)=a-1