若干直積圖的Smarandachely鄰點可區別E—全染色

董秀芳

【摘要】圖的Smarandachely鄰點可區別E-全染色是一種新的染色方法，是在Smarandachely鄰點全染色概念中弱化條件考慮Smarandachely鄰點全染色理論，也是對Smarandachely鄰點全染色概念的進一步完善.

【關鍵詞】笛卡爾積圖；關聯著色；關聯色數

每行點x，y，由于任意兩點都是不相鄰的點，所以x，y可以染同色，而每一行的頂點可以染同一色，行與行之間就可以用兩種色α1與α2色交替染，最后α3色染圖Pm∧Cn的所有邊.由點染色的過程可知：每個點上所染的顏色恰好為相鄰色集合所缺少的顏色.故上述染色過程是圖Pm∧Cn的一個3-SAVDETC.

通過以上定理完善研究了路、圈、星、扇、輪圖之間的直積圖的Smarandachely鄰點可區別全染色，得到其相應的色數，進一步驗證了鄰點可區別全染色猜想.

【參考文獻】

[1]張忠輔，張建勒，王建方.若干圖的全染色[J].中國科學A輯，1988（6）：595-600.

[2]王雙莉，張荔，李沐春.若干冠圖的鄰點可區別的V-全染色[J].蘭州交通大學學報，2012（4）：138-141.

[3]張忠輔，王建方.關于圖的全著色——一個綜述[J].數學進展，1992（4）：390-397.