T-型六角系統(tǒng)的鄰點可區(qū)別I-全色數(shù)

楊隨義

（天水師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，甘肅 天水 741001）

1 預(yù)備知識

圖染色作為圖論研究的重要方向之一，被廣泛應(yīng)用于信息計算科學(xué)、通信網(wǎng)絡(luò)、交通運輸?shù)阮I(lǐng)域，為實際問題的解決提供了重要的理論依據(jù)和最優(yōu)策略.圖染色最早起源于四色問題的研究，隨后一系列經(jīng)典染色如點染色、邊染色以及全染色等相繼被提出.[1]點染色是若干種顏色在頂點（邊）上的一個分配，且相鄰頂點（邊）分配不同的顏色，將所用的最少顏色數(shù)稱為點（邊）色數(shù).圖的全染色是若干種顏色同時在頂點和邊上的一個分配，且滿足相鄰頂點與相鄰邊以及關(guān)聯(lián)元素分配不同的顏色，類似地，將所用的最少顏色數(shù)稱為全色數(shù).1941年，Brooks證明任意一個既不是奇圈也不是完全圖的連通圖，其點色數(shù)不超過Δ.1964年前后，Vizing和Gupta分別獨立證明了任意一個圖的邊色數(shù)不超過Δ+1.此外，Vizing還猜測：任意一個圖的全色數(shù)不超過Δ+2，即后來眾所周知的全染色猜想（TCC）.染色問題已被證明是一個NP-難問題，因此，為了進(jìn)一步探索TCC猜想，國內(nèi)外學(xué)者隨后又相繼提出了一系列可區(qū)別染色.2005年，張忠輔等[1]提出了圖的鄰點可區(qū)別全染色的概念，并給出了圈、完全圖、完全二部圖等一些特殊圖類的鄰點可區(qū)別全色數(shù)，并猜測圖的鄰點可區(qū)別全色數(shù)Δ+2.此后，國內(nèi)外學(xué)者針對這一猜想展開了研究.[2，3]為了推動鄰點可區(qū)別全色數(shù)猜想的研究，張忠輔等[4]在鄰點可區(qū)別全染色的基礎(chǔ)上，提出了鄰點可區(qū)別I-全染色的概念.隨后王……