楊隨義

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

1 預備知識

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

六角系統(tǒng)作為化學圖論中重要的研究對象，受到了國內(nèi)外學者的廣泛關注.六角系統(tǒng)圖是由正六邊形所組成的平面圖網(wǎng)絡，其構型多種多樣，不同的構型其化學性質(zhì)也各不相同.T-型六角系統(tǒng)是一類特殊的六角系統(tǒng)，它是由一個正六邊形中心分別向3個間隔方向延伸n個正六邊形直鏈所構成的對稱圖，簡稱n階T-型六角系統(tǒng)鏈.最近，王文杰等[8]首先研究了T-型六角系統(tǒng)鏈的點可區(qū)別邊染色.本文以此為動機，研究了T-型六角系統(tǒng)Tn的鄰點可區(qū)別I-全色數(shù)，并得到了其鄰點可區(qū)別I-全色數(shù).

定義1.1[1]設G是階至少為2的連通圖，k是正整數(shù)，f是V(G)?E(G)到{1,2,…,k}的映射，對任意u∈V(G)，記C(u)={f(u)}?{f(uv)|uv∈E(G),v∈V(G)}.如果

(1)對于任意uv,vw∈E(G),u≠w，有

f(uv)≠f(vw)；

(2)對于任意uv∈E(G),有

f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv)；

則稱f為G的k-正常全染色，進一步，如果f還滿足

2 主要結(jié)果