一類廣義Petersen圖的2-距離染色

陳海鈺

(蘭州職業技術學院，甘肅 蘭州 730070)

0 引言

圖的染色問題是圖論研究的重要問題之一.距離染色的概念最早由F Kramer和H kramer在文獻[1-2]中提出，它是頂點染色理論的一種推廣.圖G(V,E)的2-距離染色是指正常的頂點染色，且滿足距離不大于2的任意兩個頂點染不同的顏色，記作(r,2)-DC，其中r是所用顏色數，滿足(r,2)-DC的最少顏色數稱為2-距離色數，記作χ2(G).文獻[4-7]研究了一些特殊圖類的k-距離染色；文獻[8]概述了有關平面圖的2-距離染色的研究結果.文獻[9]確定了稀疏平面圖的2-距離染色上界.本文研究了一類廣義Petersen圖P(n,2)的2-距離染色，并確定了P(n,2)的2-距離色數.

1 定義及引理

定義1[10]設圖G的頂點集為{x0,x1,…,xn-1;y0,y1,…,yn-1}，邊集為{xixi+1,xiyi,yiyi+t|i=0,1,…,n-1},其中下標取模n，且n≥5,0

引理1[4]

對于廣義Petersen圖P(n,2)，令Y0={yi|i為偶數}，Y1={yi|i為奇數}，X={x0,x1,…,xn-1}，則

由廣義Petersen圖的定義容易得到如下性質.

未做說明的符號參見文獻[11].

2 主要結論

定理1χ2(P(5,2))=10.

證明因為P(5,2)就是Petersen圖，而Petersen圖是直徑為2的10個頂點的圖.

定理2χ2(P(n,2))=5，當且僅當n=10m(其中m≥1為整數).

證明

(1)充分性

由于P(n,2)有C5子圖，所以

χ2(P(10m,2))≥5.

要證明χ2(P(10m,2))≤5，只需要給出P(10m,2)的一個(5,2)-DC.P(10,2)的(5,2)-DC如圖1所示.如果m>1，按照此方案循環染色即可.

圖1 P(10,2)的(5,2)-DC

(2)必要性

由于x0,x1,x2,y2,y0導出的子圖為5-圈，不妨用顏色1，2，3，4，5染，則y1可用的顏色有{4,5}，x3可用的顏色有{1,5}.若c(y1)=4且c(x3)=1(c(xi)表示xi所染的顏色)，則y4沒有可用的顏色，故只能c(y1)=4且c(x3)=5，或者c(y1)=5且c(x3)=1.不放設c(y1)=4且c(x3)=5，此時，P(n,2)的所有頂點的染色方案確定且唯一.即x0,x1,…,xn-1循環染顏色1，2，3，5，2，4，5，1，4，3；y0,y1,…,yn-1循環染顏色5，4，4，1，1，3，3，2，2，5.所以，當n不是10的倍數時，總存在P(n,2)的頂點沒有可行的顏色.同理可證當c(y1)=5且c(x3)=1時的情形.

定理3若n≠5且n≡0(mod 10)時，χ2(P(n,2))=6.

證明分以下3種情形，給出P(n,2)的(6,2)-DC，假設顏色集合為{0,1,2,3,4,5}.

情形1n≡0(mod 3).

令n=3m(m≥2).若m≡0(mod 2)，令m=2l(l≥1)，那么n=6l≡0(mod 2)，Y0,Y1的導出子圖為兩個不相交3l-圈，又因為X的導出子圖為3m-圈，所以X中的頂點從x0開始，依次按照下標從小到大的順序循環染顏色1，2，3；Y0中的頂點從y0開始，依次按照下標從小到大的順序循環染顏色4，5，6；Y1中的頂點從y1開始，依次按照下標從小到大的順序循環染顏色4，5，6(如圖2所示).

圖2 P(6l,2)的(6，2)-DC

若m≡1(mod 2)，令m=2l+1(l≥1)，那么

n=3(2l+1)≡1(mod 2)，

Y的導出子圖為一個n-圈.又因為X的導出子圖為3m-圈，所以X中的頂點從x0開始，依次按照下標從小到大的順序循環染顏色1，2，3；Y中的頂點從y0開始，依次按照在Y的導出n-圈中順序循環染顏色4，5，6(如圖3所示).

圖3 P(3(2l+1),2)的(6，2)-DC

情形2n≡1(mod 3).

令n=3m+1(m≥2).若m≡0(mod 2)，令m=2l(l≥1)，那么n=6l+1≡1(mod 2)，Y的導出子圖為一個n-圈，且

|Y0|=3l+1，|Y1|=3l.

圖4 P(6l+1,2)的(6，2)-DC

圖5 P(6l+4,2)的(6，2)-DC

情形3n≡2(mod 3).

令n=3m+2(m≥2).若m≡0(mod 2)，令m=2l(l≥1)，那么

n=6l+2≡0(mod 2)，

圖6 圖4P(6l+4，2)的(6，2)-DC

圖7 圖4P(6l+2，2)的(6，2)-DC

綜上，結論得證.

當n>5時，由于P(n,d)是三正則圖，與任一頂點距離為2的頂點最多有9個，依據P(n,d)的特點，在這些頂點中至少存在兩個距離大于2的頂點，所以有χ2(P(n,d))≤9.鑒于已經證明的結論，提出下面的猜想:

猜想當n>5時，有χ2(P(n,d))≤6.