兩類正則圖的鄰點全和可區別全染色

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

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

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

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

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

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

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

其中

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

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

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

1 廣義Petersen圖

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

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

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

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

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

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

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

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

2 循環圖

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

引理4當n為偶數，l為奇數時，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)中各點的權重為：φ(ai)=10(i≡0(mod 2))，φ(ai)=13(i≡1(mod 2))，證畢．

引理5當n為奇數，l為偶數時，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．