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

1、鄰點可區(qū)別全染色是指給圖的頂點和邊都染色，使得相鄰頂點及相鄰邊都染有不同顏色，而且相鄰點的色集也不相同，這里一個點的色集是指該點上的顏色及其相關(guān)聯(lián)的邊上顏色集合。其中滿足條件的最小的色數(shù)用(X)at(G)來表示．本篇論文主要對幾類圖的鄰點可區(qū)別全染色進(jìn)行了研究，其中包括圈和星圖的聯(lián)圖CmνSn的鄰點可區(qū)別全染色，Petersen圖的鄰點可區(qū)別全染色，以及Petersen圖和點的、Petersen圖和P2的、Petersen圖和P3的聯(lián)圖

2、的鄰點可區(qū)別全染色。在文中對于上述圖類的鄰點可區(qū)別全染色給出了配色方案，并對色數(shù)的下限進(jìn)行了證明和驗證。
　　 具體結(jié)果如下：
　　 對于圈和星圖的聯(lián)圖CmνSn的鄰點可區(qū)分全染色除去幾類特殊情況，得到了一般的結(jié)論如下：
　　 (X)at(CmνSn){=△+1ifn=2,m≥7orn=3m≥5orn≥m≥4orm＞n≥4=△+2ifn=1orn=1,m=3orn=3,m=3orm＞n=3≤△+2ifn=2,4≤

3、m≤6≤9ifn=3，m=4}
　　 而對于Petersen圖的鄰點可區(qū)別全染色以及Petersen圖和點的、Petersen圖和P2的、Petersen圖和P3的聯(lián)圖的鄰點可區(qū)別全染色，則是分別根據(jù)是否有相鄰的最大度點加以討論，得到相關(guān)的結(jié)論。其中Petersen圖的鄰點可區(qū)別全染色數(shù)是5，Petersen圖和點的的聯(lián)圖的全染色數(shù)是11，Petersen圖和P2的聯(lián)圖的鄰點可區(qū)別全染色數(shù)是13、Petersen圖和P3的鄰點可