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

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

2、的鄰點可區(qū)別全染色。在文中對于上述圖類的鄰點可區(qū)別全染色給出了配色方案，并對色數的下限進行了證明和驗證。
　　 具體結果如下：
　　 對于圈和星圖的聯圖CmνSn的鄰點可區(qū)分全染色除去幾類特殊情況，得到了一般的結論如下：
　　 (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的聯圖的鄰點可區(qū)別全染色，則是分別根據是否有相鄰的最大度點加以討論，得到相關的結論。其中Petersen圖的鄰點可區(qū)別全染色數是5，Petersen圖和點的的聯圖的全染色數是11，Petersen圖和P2的聯圖的鄰點可區(qū)別全染色數是13、Petersen圖和P3的鄰點可