仙人掌圖的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色

摘要： 設(shè)G為簡單圖.G的全k-染色是指k種顏色1,2,…,k對圖G的全體頂點(diǎn)及邊的一個(gè)分配.設(shè)c是圖G的一個(gè)全k-染色,任意的x∈V(G),稱■為點(diǎn)x的擴(kuò)展和,其中N(x)={y∈V(G)|xy∈E(G)}.稱圖G的全k-染色c為鄰點(diǎn)被擴(kuò)展和可區(qū)別(簡記為NESD),如果w(x)≠w(y),其中xy∈E(G).使得圖G存在NESD全k-染色的最小值k被稱為圖G的鄰點(diǎn)被擴(kuò)展和可區(qū)別全色數(shù),簡記為egndi_∑(G).本文利用數(shù)學(xué)歸納法探討了仙人掌圖的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色,并證明了這類圖的鄰點(diǎn)被擴(kuò)展和可區(qū)別全色數(shù)不超過2.該結(jié)論說明Flandrin等人提出的NESDTC猜想對于仙人掌圖是成立的. （共6頁）