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

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

3、，七為正整數．函數，是從V(G)∪E(G)到C={1.2.…，k}(也記作：C=[k])的一個映射： 對于任意頂點u ∈ V(G)．記C(u)={f(u)}∪{f(uv·)|uv ∈ E(G)}．-C(u)=C-C(u)： (1)對任意邊uv,uw ∈ E(G),且u≠w，有f(uv)≠f(uw); (2)對任意邊uv ∈ E(G)．且u≠v．有f(u)≠f(u)．f(u)≠f(uv)，f(uv)≠f(u)：

4、 (3)對于任意邊uv ∈ E(G)．且u≠v，有C(u)≠C(v)． 若滿足條件(1)．(2)．則稱f為圖G的一個正常k-全染色(簡記為k-TC)． 若滿足條件(1)．(2)，(3)．則稱f為圖G的一個k-鄰點可區(qū)別的全染色(簡記為k-AVDTC)． 圖G的全色數為XT(G)=min{k圖G有k-TC}． 圖G的鄰點可區(qū)別的全色數為Xat(G)=min{k|圖G有k-AV DTC}． 下面兩

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

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

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