常景智，楊超，程銀萬，王芹，姚兵

1.上海工程技術(shù)大學 數(shù)理與統(tǒng)計學院 智能計算與應用統(tǒng)計研究中心，上海 201620；2.西北師范大學 數(shù)學與統(tǒng)計學院，蘭州 730070

圖的可區(qū)別染色問題是圖論中的經(jīng)典問題之一，隨著可區(qū)別染色問題被廣泛應用于計算機科學、生物學以及網(wǎng)絡安全等領域，這一問題被越來越多的國內(nèi)外學者所研究．近年來，關于把點和邊所染顏色相加的可區(qū)別染色問題引起了人們的極大關注．文獻[1]介紹和研究了圖的鄰和可區(qū)別邊染色，并提出下述著名的1-2-3猜想：

猜想1[1](1-2-3猜想) 設G為一個階數(shù)至少為3的簡單連通圖，則gndiΣ(G)≤3．

文獻[2]證明了階數(shù)至少為3的簡單連通圖的鄰和可區(qū)別邊色數(shù)不超過5．關于鄰和可區(qū)別邊染色的相關研究見文獻[3-6]．文獻[7]提出了圖的鄰和可區(qū)別全染色的概念，并給出了此定義下的1-2猜想：

猜想2[7](1-2猜想) 設G為一個簡單連通圖，則tgndiΣ(G)≤2．

文獻[8]得到了任意圖的鄰和可區(qū)別全色數(shù)不超過3．文獻[9]考慮把任意點的關聯(lián)邊與其鄰點所染顏色相加，定義了圖的鄰點被擴展和可區(qū)別全染色，且得到了一些特殊圖的鄰點被拓展和可區(qū)別全色數(shù)．文獻[10]研究了仙人掌圖的鄰點被拓展和可區(qū)別全染色．不僅如此，文獻[9]又在鄰點被擴展和可區(qū)別全染色的基礎上考慮加上點本身的顏色，介紹了下述關于圖的一類新染色——鄰點全和可區(qū)別全染色：

其中

N(x)={y∈V(G)|xy∈E(G)}

對任意的邊uv∈E(G)，如果有φ(u)≠φ(v)成立，則稱f是圖G的一個鄰點全和可區(qū)別(簡記NFSD)k-全染色．圖G的鄰點全和可區(qū)別全染色中最小的k值稱為G的鄰點全和可區(qū)別全色數(shù)，記為fgndiΣ(G)．

本文研究了廣義Petersen圖和循環(huán)圖的鄰點全和可區(qū)別全染色問題，確定了它們的鄰點全和可區(qū)別全色數(shù)．文中涉及的染色均為非正常的，不失一般性，約定下文證明過程中凡是未被染色的點和邊均染顏色1．

1 廣義Petersen圖

定理1當n為偶數(shù)，k為奇數(shù)時，fgndiΣ(P(n，k))=2； 其他情形時，fgndiΣ(P(n，k))≤3．

由定義2知P(n，k)是一類三正則圖，則fgndiΣ(P(n，k))≥2．定理1分以下3個引理證明：

引理1當n為偶數(shù)，k為奇數(shù)時，fgndiΣ(P(n，k))=2．

證定義P(n，k)的一個2-全染色f：f(aiai+1)=f(aibi)=f(aibi+k)=1，f(ai)=2(i為奇數(shù))，f(bi)=2(i為偶數(shù))．由染色f可得P(n，k)中各點的權(quán)重為：φ(ai)=10(i為奇數(shù))，φ(ai)=8(i為偶數(shù))，φ(bi)=8(i為奇數(shù))，φ(bi)=10(i為偶數(shù))．因bi總與bi+k相連，所以內(nèi)圈中的相鄰點下標的奇偶性不同，則有φ(bi)=10(i為偶數(shù))≠φ(bi)=8(i為奇數(shù))，證畢．

引理2當n為偶數(shù)，k為偶數(shù)時，fgndiΣ(P(n，k))≤3．

證根據(jù)不交圈的長度p，分以下3種情形討論：

引理3當n為奇數(shù)時，fgndiΣ(P(n，k))≤3．

情況2 對內(nèi)圈染色：令f(ai)=1，f(bi)=3．當p?2(mod 3)時，令當p≡2(mod 3)時，令

2 循環(huán)圖

由定義3知C(n，l)是正則圖，則fgndiΣ(C(n，l))≥2．定理2分以下4個引理證明：

引理4當n為偶數(shù)，l為奇數(shù)時，fgndiΣ(C(n，l))=2．

證定義C(n，l)的一個2-全染色f如下：f(aiai+1)=f(aiai+l)=1，f(ai)=2(i≡1(mod 2))．由染色f可得C(n，l)中各點的權(quán)重為：φ(ai)=10(i≡0(mod 2))，φ(ai)=13(i≡1(mod 2))，證畢．

引理5當n為奇數(shù)，l為偶數(shù)時，fgndiΣ(C(n，l))≤3．

引理7當n=2l時，fgndiΣ(C(n，l))=2．

情形2 當l=3時，令f(a1a4)=f(a3a4)=f(a4a5)=f(a4)=2，得φ(a1)=φ(a3)=φ(a5)=9，φ(a2)=φ(a6)=7，φ(a4)=11．

情形3 當l=4時，令f(a1a5)=f(a3a7)=f(a3a4)=f(a4a5)=f(a5a6)=f(a5)=2，得φ(a1)=φ(a3)=φ(a6)=9，φ(a2)=φ(a8)=7，φ(a4)=10，φ(a5)=11，φ(a7)=8．

情形4 當l=5時，令f(a1a6)=f(a3a8)=f(a4a9)=f(a2a3)=f(a5a6)=f(a6a7)=f(a9a10)=f(a4)=2，得φ(ai)=9(i=1，3，5，7，9)，φ(a2)=φ(a4)=φ(a8)=φ(a10)=8，φ(a6)=11．