圖的鄰點(diǎn)可區(qū)別的全染色.pdf

1、染色問(wèn)題是圖論研究的經(jīng)典領(lǐng)域，是圖論研究中一個(gè)很活躍的話題．染色問(wèn)題及許多圖理論均源自四色問(wèn)題的研究，隨著染色問(wèn)題在現(xiàn)實(shí)中被廣泛應(yīng)用，各類染色問(wèn)題被相繼提出并加以發(fā)展，研究． 圖G的一個(gè)正常膏一染色是將k種顏色分配給G的頂點(diǎn)集V(G)使得兩相鄰頂點(diǎn)的顏色不同．定義色數(shù)為X(G)=min{k|圖G有k-染色}[1].類似的，圖G的一個(gè)正常k-邊染色是將k種顏色分配給G的邊集E(G)．使得有公共端點(diǎn)的兩邊的顏色不同，邊色數(shù)X'(G)

2、=min{k|圖G有k-邊染色).[1]全染色的概念是對(duì)點(diǎn)染色和邊染色的推廣，是圖染色的一個(gè)傳統(tǒng)問(wèn)題，由Vizing(1964)[3]．Behzad(1965)[4][5]各自獨(dú)立提出．圖的全染色是對(duì)圖的點(diǎn)，邊進(jìn)行染色使得相鄰或相關(guān)聯(lián)的元素顏色不同．在全染色的基礎(chǔ)上張忠輔提出了鄰點(diǎn)可區(qū)別的全染色概念并給出了相應(yīng)的猜想和兩個(gè)引理[2]. 張忠輔給出的鄰點(diǎn)可區(qū)別的全染色定義是這樣的： 設(shè)圖G(V.E)為階至少為2的簡(jiǎn)單連通圖

3、，七為正整數(shù)．函數(shù)，是從V(G)∪E(G)到C={1.2.…，k}(也記作：C=[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,uw ∈ E(G),且u≠w，有f(uv)≠f(uw); (2)對(duì)任意邊uv ∈ E(G)．且u≠v．有f(u)≠f(u)．f(u)≠f(uv)，f(uv)≠f(u)：

4、 (3)對(duì)于任意邊uv ∈ E(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)． 圖G的全色數(shù)為XT(G)=min{k圖G有k-TC}． 圖G的鄰點(diǎn)可區(qū)別的全色數(shù)為Xat(G)=min{k|圖G有k-AV DTC}． 下面兩

5、個(gè)關(guān)于鄰點(diǎn)可區(qū)別的全染色的引理[2]: 對(duì)任意階為n(n=|V(G)1≥2)的簡(jiǎn)單連通圖G．鄰點(diǎn)可區(qū)別全色數(shù)Xat(G)存在，并且Xat(G)≥△(G)+1. 若圖G(V.E)有兩相鄰的最大度頂點(diǎn)，則Xat(G)≥△(G)+2. 張忠輔在文獻(xiàn)[2]中給出了關(guān)于鄰點(diǎn)可區(qū)別全染色的猜想： 對(duì)任意階為n(n=|V(G)|≥2)的簡(jiǎn)單連通圖G．有Xat(G)≤△(G)+3. 對(duì)于路，圈，完全圖，完全二部圖

6、，星，扇，輪，樹等特殊圖類目前已得出了其具體的鄰點(diǎn)可區(qū)別的全色數(shù)，并且滿足上述猜想．關(guān)于上述特殊圖的Mycielski圖，聯(lián)圖和乘積圖的鄰點(diǎn)可區(qū)別的全色數(shù)已有一些結(jié)果．另外，Petersen圖，Hewood圖，Tomassen圖及Wn的Hajos sum圖的鄰點(diǎn)可區(qū)別的全染色也已得到一些結(jié)果． 確定一個(gè)給定圖的鄰點(diǎn)可區(qū)別的全色數(shù)是NP-困難的，本文對(duì)一些特殊圖及在某些圖運(yùn)算下的圖的鄰點(diǎn)可區(qū)別的全染色進(jìn)行了研究． 在本文我

7、們得到如下結(jié)論: 圖的插入運(yùn)算：已知圖G．H且有|V(G)|=|E(H)|．圖G插入日是指用G的所有頂點(diǎn)一一對(duì)應(yīng)地剖分H的所有邊，原G中的邊不變． 點(diǎn)擴(kuò)充圖：圖G的v(H)點(diǎn)擴(kuò)充圖是指將G的某頂點(diǎn)v，用圖H代替，但v的每個(gè)鄰點(diǎn)只分別與H的一點(diǎn)相鄰，即:v的每個(gè)鄰點(diǎn)的度不變． Hajos sum[11]：兩個(gè)點(diǎn)不交的圖G1.G2的Hajos sum:G=(G1.X1y1)-(G2.x2y2)將X1.X2粘合為一點(diǎn)x