劉利群 (長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院,湖北 荊州 434023)

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

D(β)-點(diǎn)可區(qū)別I-全染色的上界研究

劉利群 (長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院,湖北 荊州 434023)

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

設(shè)G是簡(jiǎn)單圖，若圖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(β)-點(diǎn)可區(qū)別I-全染色；D(β)-點(diǎn)可區(qū)別I-全色數(shù);上界

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

1 基本概念

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

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

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

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

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

2 主要結(jié)果與證明

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

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

第2步 取一種新顏色a,對(duì)G的每個(gè)頂點(diǎn)隨機(jī)獨(dú)立的挑選它的一條關(guān)聯(lián)邊用新顏色a重染(這時(shí),邊e=uv被新顏色a重染的概率是1/(deg(u))+1/(deg(v)))。

第3步 在第2步完成后,另取一種新顏色b,再對(duì)G的每個(gè)頂點(diǎn)隨機(jī)獨(dú)立的挑選它的一條關(guān)聯(lián)邊用新顏色b重染。注意:新顏色b可能覆蓋新顏色a。

第4步 在第3步完成后,另取一種新顏色c,再對(duì)G的每個(gè)頂點(diǎn)隨機(jī)獨(dú)立的挑選它的一條關(guān)聯(lián)邊用新顏色c重染。注意:新顏色c可能覆蓋新顏色a、b。

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

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

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

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

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

然后計(jì)算相關(guān)事件數(shù)。對(duì)類型(I)的每個(gè)事件Ae,f,在D中Ae,f的相關(guān)點(diǎn)至多與類型(I)的4Δ個(gè)事件相關(guān),至多與類型(II)的3Δ個(gè)事件相關(guān);對(duì)類型(II)的每個(gè)事件Bu,v,在D中Bu,v的相關(guān)點(diǎn)至多與類型(I)的4Δ2個(gè)事件相關(guān),至多與類型(II)的2Δ2個(gè)事件相關(guān)。

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

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

(1)

因?yàn)?

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

(2)

對(duì)所有實(shí)數(shù)x≥2,有(1-1/x)x≥1/4,所以當(dāng)Δ≥67時(shí)有：

(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設(shè)G1、G2是連通圖,則有：

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

證明設(shè)vw∈E(G),若將v、w分別用Q2的拷貝代替,其頂點(diǎn)分別為vi、wi(1≤i≤4),其中vi與wi相鄰。于是得到積圖G×Q2,其中Gvw(將v、w分別用Q2的拷貝代替后得到的圖)與Q3同構(gòu)。設(shè)η是G的一個(gè)D(2)-點(diǎn)可區(qū)別正常邊染色,所用顏色為{1,2,…,m};θ是Q2的一個(gè)D(2)-點(diǎn)可區(qū)別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所示)。

分別用η染色法及θ染色法對(duì)G×Q2進(jìn)行著色,設(shè)在η染色法下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設(shè)G(V,E)是連通圖, 則有:

證明設(shè)vw∈E(G),若將v,w分別用Q3的拷貝代替,其頂點(diǎn)分別為vi、wi(1≤i≤8),其中vi與wi相鄰。于是得到積圖G×Q3。設(shè)η是G的一個(gè)D(2)-點(diǎn)可區(qū)別正常邊染色,所用顏色為{1,2,…,m};θ是Q2的一個(gè)D(2)-點(diǎn)可區(qū)別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所示)。

分別用η染色法及θ染色法對(duì)G×Q3進(jìn)行著色, 設(shè)v、w是G的2個(gè)頂點(diǎn),且v、w的距離不超過(guò)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設(shè)G(V,E)是連通圖, 則有：

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

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

類似結(jié)論可推廣到D(β)-點(diǎn)可區(qū)別I-全染色:

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

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

證明設(shè)vw∈E(G),若將v、w分別用Q3的拷貝代替,其頂點(diǎn)分別為vi、wi(1≤i≤8),其中vi與wi相鄰。于是得到積圖G×Q3。設(shè)η是G的一個(gè)D(β)-點(diǎn)可區(qū)別正常邊染色,所用顏色為{1,2,…,m};θ是Q2的一個(gè)6-D(β)-點(diǎn)可區(qū)別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設(shè)G(V,E)是連通圖, 則有:

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

當(dāng)n=2r+1(r為正整數(shù)),由定理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]張忠輔, 李敬文, 陳祥恩,等.圖的距離不大β的任意兩點(diǎn)可區(qū)別的邊染色[J].數(shù)學(xué)學(xué)報(bào), 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)-點(diǎn)可區(qū)別正常邊染色[J].山東大學(xué)學(xué)報(bào), 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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61163037；61163054)；西北師范大學(xué)“知識(shí)與科技創(chuàng)新工程”項(xiàng)目(nwnu-kjcxgc-03-61)。

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