D(β)-點可區別I-全染色的上界研究

劉利群 (長江大學信息與數學學院,湖北 荊州 434023)

陳祥恩 (西北師范大學數學與信息科學學院，甘肅 蘭州 730079)

D(β)-點可區別I-全染色的上界研究

劉利群 (長江大學信息與數學學院,湖北 荊州 434023)

陳祥恩 (西北師范大學數學與信息科學學院，甘肅 蘭州 730079)

設G是簡單圖，若圖G的全染色f滿足:①?uv,vw∈E(G)，有f(uv)≠f(vw); ②?uv∈E(G),u≠v,有f(u)≠f(v); ③?u,v∈V(G),0

D(β)-點可區別I-全染色；D(β)-點可區別I-全色數;上界

圖的染色問題是圖論中具有重要實際意義和理論意義的研究課題之一。筆者考慮的圖均為沒有孤立邊,最多有一個孤立點的有限無向單圖。1997年,Burris A C和Schelp R H引入了圖的點可區別的正常邊染色(即強邊染色)的概念[1], 此后,許多學者對圖的染色的理論作了大量的研究。文獻[1-4]研究了點可區別的正常邊染色；文獻[5]提出了鄰點可區別正常邊染色(即鄰強邊染色)的概念;文獻[6-8]研究了D(β)-點可區別的正常邊染色; 文獻[9-10]研究了全染色。

1 基本概念

定義1[3]G(V,E)是階至少為3的連通圖,α、β是正整數，f是從E(G)到{1,2,…,α)的一個映射。對?e∈E(G),稱f(e)為邊e的顏色。對任意?x∈V(G),令S(x)表示與x關聯的邊的顏色所構成的集合, 稱為點x的色集合。若f是圖G的正常邊染色, 且當u、v∈V(G),0

定義2圖G的正常點染色是對圖G的每個頂點都指定一種顏色,使得沒有2個相鄰的頂點指定為相同的顏色。如果這些顏色選自于一個有k種顏色的集合而不管k種顏色是否都用到,這樣的染色稱為k-正常點染色。若f是G的一個使用了k種顏色的正常點染色,滿足:當u、v∈V(G),0

定義3圖G的全染色叫做圖G的正常全染色,如果以下3個條件被滿足，條件(v)：相鄰的3個頂點不能染相同的顏色；條件(e)：相鄰的2條邊不能染相同的顏色；條件(i)：任意的點和與之關聯的邊不能染相同的顏色。

如果圖G的全染色只滿足條件(e),這樣的全染色稱為圖G的VI-全染色；如果圖G的全染色滿足條件(v)和條件(e),這樣的全染色稱為圖G的I-全染色。

定義4若f是G的一個使用了k種顏色的全染色,滿足:①對任意相鄰的邊e1、e2,有f(e1)≠f(e2);

2 主要結果與證明

證明假設圖G(V,E)已給出,分以下4個步驟對圖G進行全染色。

第1步 由Vizing定理,可先用Δ(G)+1種顏色對G進行正常邊染色，再用Δ(G)+1種顏色對G進行正常點染色,這樣就得到了G的全染色。

第2步 取一種新顏色a,對G的每個頂點隨機獨立的挑選它的一條關聯邊用新顏色a重染(這時,邊e=uv被新顏色a重染的概率是1/(deg(u))+1/(deg(v)))。

第3步 在第2步完成后,另取一種新顏色b,再對G的每個頂點隨機獨立的挑選它的一條關聯邊用新顏色b重染。注意:新顏色b可能覆蓋新顏色a。

第4步 在第3步完成后,另取一種新顏色c,再對G的每個頂點隨機獨立的挑選它的一條關聯邊用新顏色c重染。注意:新顏色c可能覆蓋新顏色a、b。

下面證明以下2點成立的概率為正:①此全染色滿足沒有相鄰2條邊或相鄰的2點著色相同;②此全染色是鄰點可區別的即對任意相鄰2點u、v(uv∈E(G)),有S(u)≠S(v)。

為此,定義如下壞事件:(Ⅰ)對每對相鄰的邊e、f∈E(G),令Ae,f表示e和f被染成同種顏色的事件；(Ⅱ)對每一條邊e=uv∈E(G),令Bu,v表示u和v的關聯邊是正常著色且S(u)=S(v)的事件。下面證明上述壞事件都不發生的概率為正。

構造相關圖D,其中D的頂點是以上2種類型的所有事件,設EX、EY是D的2個頂點(每個X、Y是一對相鄰邊,或者是和一條邊相鄰的所有邊及其這條邊本身。EX和EY是相鄰的當且僅當X和Y至少包含一條公共邊。由于EX的每個事件發生依賴于X的邊,從而D是事件的相關圖。首先,需要計算每個壞事件發生的概率,有以下2條成立:對類型(Ⅰ)的每個事件Ae,f,有Pr(Ae,f)≤3/δ2;對類型(Ⅱ)的每個事件Bu,v,有Pr(Bu,v)≤6/d3。

下面首先證明Pr(Ae,f)≤3/δ2。若事件Ae,f發生,則e,f被同種新顏色重染。設e的端點是w1、w2,f的端點是w2、w3,deg(wi)=di(i=1,2,3),若e、f都被顏色x(x=a,b,c)重染,有以下3種情況:(i)作為w1的關聯邊e被顏色x重染的概率為1/d1,同時作為w2的關聯邊f被顏色x重染的概率為1/d2,此時e、f同時被一種新顏色重染的概率為1/(d1d2);(ii)作為w1的關聯邊e被顏色x重染的概率為1/d1,同時作為w3的關聯邊f被顏色x重染的概率為1/d3,此時e、f同時被一種新顏色重染的概率為1/(d1d3);(iii)作為w2的關聯邊e被顏色x重染的概率為1/d2,同時作為w3的關聯邊f被顏色x重染的概率為1/d3,此時e、f同時被一種新顏色重染的概率為1/(d2d3)。故e、f同時被一種新顏色重染的概率不大于1/(d1d2)+1/(d1d3)+1/(d2d3)≤3/δ2。

其次證明Pr(Bu,v)≤6/d3。若事件Bu,v發生,則u和v有相同的色集合,且它們的色集合中都包含有a、b、c這3種顏色中至少一種。下面分以下幾種情況進行討論:(i)用Δ(G)+1種顏色對G進行全染色后,若u和v有相同的色集合,則Pr(Bu,v)≤3!/d3=6/d3;(ii)用Δ(G)+1種顏色對G進行全染色后,若u和v的色集合中有1種不同的顏色,則Pr(Bu,v)≤3×(3!)/d4≤6/d3;(iii)用Δ(G)+1種顏色對G進行全染色后,若u和v的色集合中有2種不同的顏色,則Pr(Bu,v)≤6×(3!)/d5≤6/d3;(iv)用Δ(G)+1種顏色對G進行全染色后,若u和v的色集合中有3種不同的顏色,則Pr(Bu,v)≤6×(3!)/d6≤6/d3;(v)用Δ(G)+1種顏色對G進行全染色后,若u和v的色集合中有大于3種不同的顏色,則Pr(Bu,v)=0。故對類型(II)的每個事件Bu,v,Pr(Bu,v)有≤6/d3。

然后計算相關事件數。對類型(I)的每個事件Ae,f,在D中Ae,f的相關點至多與類型(I)的4Δ個事件相關,至多與類型(II)的3Δ個事件相關;對類型(II)的每個事件Bu,v,在D中Bu,v的相關點至多與類型(I)的4Δ2個事件相關,至多與類型(II)的2Δ2個事件相關。

應用一般局部引理,可構造常數。令8/Δ2,1/(2Δ2)分別表示和(Ⅰ)、(Ⅱ)中的事件相應的常數,那么為了滿足一般局部引理的條件,需要證明以下2個不等式成立:

Pr(Ae,f)≤(8/Δ2)(1-8Δ2)4Δ(1-1/2Δ2)3Δ

(1)

因為:

Pr(Bu,v)≤(1/2Δ2)(1-8/Δ2)4Δ2(1-1/2Δ2)2Δ2

(2)

對所有實數x≥2,有(1-1/x)x≥1/4,所以當Δ≥67時有：

(8/Δ2)(1-8/Δ2)4Δ(1-1/2Δ2)3Δ≥(8/Δ2)(1/4)32/Δ+3/2Δ=(8/Δ2)(1/2)67/Δ>4/Δ2

(1/2Δ2)(1-8/Δ2)4Δ2(1-1/2Δ2)2Δ2≥(1/2Δ2)(1/4)32+1=1/(267Δ2)

故定理1得證。

定理2設G1、G2是連通圖,則有：

定理3設G(V,E)是連通圖, 則有:

證明設vw∈E(G),若將v、w分別用Q2的拷貝代替,其頂點分別為vi、wi(1≤i≤4),其中vi與wi相鄰。于是得到積圖G×Q2,其中Gvw(將v、w分別用Q2的拷貝代替后得到的圖)與Q3同構。設η是G的一個D(2)-點可區別正常邊染色,所用顏色為{1,2,…,m};θ是Q2的一個D(2)-點可區別I-全染色,所用顏色為{a,b,c,d},其中f(v1)=f(v1v2)=a,f(v2)=f(v2v3)=b,f(v3)=f(v3v4)=c,f(v4)=f(v1v4)=d(如圖1所示)。

分別用η染色法及θ染色法對G×Q2進行著色,設在η染色法下G中一條邊vw著顏色t∈[1,m],v,w的色集合分別為X,Y(顯然X≠Y)。將G中所有著t色的邊按下述方法改變顏色:v1w1改成顏色b,v2w2改成顏色c,v3w3改成顏色d,v4w4改成顏色a。則有:

S(v1)=(X|t)∪{a,b,d}S(v2)=(X|t)∪{a,b,c}S(v3)=(X|t)∪{b,c,d}

S(v4)=(X|t)∪{a,c,d}S(w1)=(Y|t)∪{a,b,d}S(w2)=(Y|t)∪{a,b,c}

S(w3)=(Y|t)∪{b,c,d}S(w4)=(Y|t)∪{a,c,d}

圖1 圖θ2 圖2 圖θ3

定理4設G(V,E)是連通圖, 則有:

證明設vw∈E(G),若將v,w分別用Q3的拷貝代替,其頂點分別為vi、wi(1≤i≤8),其中vi與wi相鄰。于是得到積圖G×Q3。設η是G的一個D(2)-點可區別正常邊染色,所用顏色為{1,2,…,m};θ是Q2的一個D(2)-點可區別I-全染色,所用顏色為{a,b,c,d},其中:

f(v1)=f(v8)=f(v1v2)=f(v6v7)=f(v4v8)=a

f(v2)=f(v7)=f(v1v5)=f(v2v3)=f(v7v8)=b

f(v3)=f(v6)=f(v1v4)=f(v3v7)=f(v5v6)=c

f(v4)=f(v5)=f(v3v4)=f(v2v6)=f(v5v8)=d(如圖2所示)。

分別用η染色法及θ染色法對G×Q3進行著色, 設v、w是G的2個頂點,且v、w的距離不超過2，v、w在η染色法下的色集合分別為X,Y(顯然XY)。則有:

S(v1)=S(v7)=X∪{a,b,c}S(v2)=S(v8)=X∪{a,b,d}

S(v3)=S(v5)=X∪{b,c,d}S(v4)=S(v6)=X∪{a,c,d}

S(w1)=S(w7)=Y∪{a,b,c}S(w2)=S(w8)=Y∪{a,b,d}

S(w3)=S(w5)=Y∪{b,c,d}S(w4)=S(w6)=Y∪{a,c,d}

定理5設G(V,E)是連通圖, 則有：

證明當n=2r(r為正整數),由定理3,有：

當n=2r+1(r為正整數),由定理3及定理4,有：

類似結論可推廣到D(β)-點可區別I-全染色:

定理6設G(V,E)是連通圖, 則有:

定理7設G(V,E)是連通圖, 則有:

證明設vw∈E(G),若將v、w分別用Q3的拷貝代替,其頂點分別為vi、wi(1≤i≤8),其中vi與wi相鄰。于是得到積圖G×Q3。設η是G的一個D(β)-點可區別正常邊染色,所用顏色為{1,2,…,m};θ是Q2的一個6-D(β)-點可區別I-全染色,所用顏色為{a,b,c,d,e,h}，其中：

f(v1)=f(v7)=f(v1v2)=f(v6v7)=af(v2)=f(v8)=f(v2v3)=f(v7v8)=b

f(v3)=f(v3v4)=f(v5v8)=cf(v4)=f(v1v4)=f(v5v6)=d

f(v5)=f(v1v5)=(v3v7)=ef(v6)=f(v2v6)=f(v4v8)=h

定理8設G(V,E)是連通圖, 則有:

證明當n=2r(r為正整數),由定理3,有：

當n=2r+1(r為正整數),由定理3及定理4,有:

因此有:

[1]Burris A C, Schelp R H.Vertex-distinguishing proper edge-colorings[J].J of Graph Theory,1977,26:73-82.

[2] Bazgan C, Harkat-Benhamdine A,Li Hao and Wozniak M. On the vertex-distinguishing proper edge-colorings of graphs[J]. Combin Theory B, 1999, 75: 288-301.

[3] Balister P N, Bollobás B and Schelp R H. vertex-distinguishing colorings of graphs with Δ(G)=2[J]. Discrete Math, 2002, 252(1-3): 17-29.

[4] Balister P N, Riordan O M and Schelp R H. Vertex-distinguishing edge colorings of graphs[J]. Graph Theory, 2003, 42: 95-109.

[5] Zhang Zhongfu，Liu Linzhong，Wang Jianfang. Adjacent Strong Edge Coloring of Graphs[J]. Applied Mathematics Letters,2002, 15: 623-626.

[6]張忠輔, 李敬文, 陳祥恩,等.圖的距離不大β的任意兩點可區別的邊染色[J].數學學報, 2006, 49(3): 703-708.

[7]Akbari S,Bidkhori H,and Nosrati N.r-strong edge colorings of graphs [J]. Discrete Mathematics, 2006, 306:3005-3010.

[8]劉利群，陳祥恩.路和圈上的錐的D(2)-點可區別正常邊染色[J].山東大學學報, 2008, 43(2): 87-97.

[9]ZHANG Zhongfu,QIU Pengxiang,XU Baogen,et al.Vertex-distinguishing total colorings of graphs[J]. Ars Combinatoria,2008,87:33-45.

[10]CHEN Xiang-en, GAO Yu-ping, YANG Sui-yi. Various General Total colorings of Graphs[J]. Journal of Jishou University(Natural Science Edition), 2011, 32(1):1-3.

[11]Balister P N,Gy?ri E,Lehel J,et al. Adjacent Vertex Distinguishing Edge Colorings[J]. SIAM Journal on Discrete Mathematics, 2007, 21(1): 237-250.

[12]Hatami H. Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number[J]. Combin Theory, Ser B, 2005, 95:246-256.

[13]Alon N, Spencer J. The Probabilistic Method[M]. New York：John Wiley & Sons Inc，1992.

[14]Molloy M, Reed B. Graph Colouring and the Probabilistic Method[M]. New York：Springer, 2002.

[編輯] 洪云飛

O157.5

A

1673-1409(2013)22-0001-05

2013-05-20

國家自然科學基金資助項目(61163037；61163054)；西北師范大學“知識與科技創新工程”項目(nwnu-kjcxgc-03-61)。

劉利群(1977-)，女，碩士，講師，現主要從事圖論及其應用方面的教學與研究工作。