關于圖的鄰點可區別全色數的上界研究

劉利群,陳祥恩

(1.長江大學信息與數學學院,湖北 荊州 434023;2.西北師范大學數學與信息科學學院,甘肅 蘭州 730079)

關于圖的鄰點可區別全色數的上界研究

劉利群1,陳祥恩2

(1.長江大學信息與數學學院,湖北 荊州 434023;2.西北師范大學數學與信息科學學院,甘肅 蘭州 730079)

圖G的鄰點可區別全染色是指G存在一個正常全染色f使得任意相鄰兩點有不同的色集合.本文主要研究鄰點可區別正常全色數的上界,目前鄰點可區別全染色的一個較好的上界是?+C+20,本文用概率方法改進了這個結果,得到了鄰點可區別全色數的一個較小上界?+C+3.

鄰點可區別全染色;鄰點可區別全色數;上界

1 引言

染色問題是圖論中具有重要實際意義和理論意義的研究課題之一.1965年,Bahzad和Vizing各自獨立提出了圖的全染色的概念和猜想.2004年,文獻[1-2]提出了圖的鄰點可區別全染色的概念和猜想.文獻[3-4]對圖的全染色作了進一步研究,得到了一些較好的結果.文獻[5]得到了鄰點可區別全染色的一個上界?+C+20.本文嘗試通過應用局部引理,得到了鄰點可區別全色數的一個較小的上界?+C+3.

下面給出將要用到的一些概念與定理.

定義1[1]G(V,E)是階至少為2的連通圖,k是正整數,f是從V(G)∪E(G)到{1,2,···,k}的一個映射.對任意u∈V(G),記

2 主要結果及證明

定理1 設G(V,E)是連通圖,若

證明 假設圖G(V,E)已給出,分以下四個步驟對圖G的邊進行染色:

第一步由引理3,可先用?(G)+C種顏色對G進行正常全染色.

第二步取一種新顏色a,對G的每個頂點隨機獨立的挑選它的一條關聯邊用新顏色a重染.這時,邊e=uv被新顏色a重染的概率是

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

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

下面將證明以下兩點成立的概率為正:

1.著色仍然正常即沒有相鄰兩條邊或相鄰的兩點著色相同或相關聯的點與邊著色相同;

2.著色是鄰點可區別的即對任意兩點u,v∈V(G)(1≤d(u,v)≤2),有C(u)?=C(v).為此,定義如下壞事件:

(I)對每對相鄰的邊{e,f∈E(G)},令Ae,f表示e和f被染成同種顏色的事件.

(II)對每一條邊

令Bu,v表示u和v的關聯邊是正常著色且C(u)=C(v)的事件.

下面證明上述事件都不發生的概率為正.

構造相關圖D,其中D的頂點是以上二種類型的所有事件,設EX,EY是D的兩個頂點(每個X,Y是一對相鄰邊,或者是和一條邊相鄰的所有邊及其這條邊本身.EX和EY是相鄰的當且僅當X和Y至少包含一條公共邊.由于EX的每個事件發生依賴于X的邊,從而D是事件的相關圖.

首先,需要計算每個壞事件發生的概率,有以下三條成立:

1)對類型(I)的每個事件Ae,f,有

[1]張忠輔,陳祥恩,李敬文,等.關于圖的鄰點可區別全染色[J].中國科學:A輯,2004,34(5):577-583.

[2]Zhang Zhongfu,Chen X iang′en,Li Jingwen,et al.On the ad jacent vertex distinguishing total coloring of graph[J].Science in China:Ser A,2005,48(3):289-299.

[3]Zhang Zhongfu,Yao Bing.A note on the ad jacent vertex distinguishing total chromatic number of graph[J]. Journal of Lanzhou Jiaotong University:Natural Science,2006,23(6):143-145.

[4]M olloy M,Reed B.A bound on the total chromatic number[J].Combinatorica,1998,18:241-280.

[5]晁福剛,張忠輔,強會英.圖的鄰點可區別全色數的一個上界[J].純粹數學與應用數學,2010,26(1):91-95.

[6]A lon N,Spencer J.The Probabilistic Method[M].New York:W iley,1992.

[7]M olloy M,Reed B.G raph Coloring and the Probabilistic M ethod[M].New York:Springer,2002.

[8]Yap H P.Total Coloring of G raphs[M].New York:Springer,1996.

[9]Bondy J A,M urty U SR.G raph Theory with App lications[M].London:London M acm illan Press,1976.

[10]Dietel R.G raph Theory[M].New York:Springer,1997.

On an upper bound for ad jacen t vertex d istinguish ing total ch rom atic num ber of graphs

Liu Liqun1,Chen Xiang′en2

(1.College of In form ation and M athem atics,Yangtze University,Jingzhou 434023,China; 2.College of M athem atics and In form ation Science,Northwest Norm al University,Lanzhou 730079,China)

A proper total coloring of the graph G is called ad jacent vertex distinguishing total coloring,for any two ad jacent vertices u,v∈V(G),we have C(u)?=C(v),where C(u)is called color set of vertex u.Inthis paper, we study the upper bound on the ad jacent vertex distinguishing total chromatic number.Δ+C+20is a good conclusion of the upper bound on the ad jacent vertex distinguishing total chrom atic number of graphs up till now.By probability m ethod,we obtained the conclusion that a upper bound on the ad jacent vertex distinguishing total chrom atic number isΔ+C+3 in som e condition in this paper.

ad jacent vertex distinguishing total coloring,ad jacent vertex distinguishing total chrom atic number,upper bound

O157.5

A

1008-5513(2012)06-0744-05

2011-12-16.

國家自然科學基金(61163037,61163054).

劉利群(1977-),碩士,講師,研究方向：圖論及其應用.

2010 M SC:05C15