蔡學鵬，任佰通，馮苗苗

?

圖的鄰點強可區(qū)別V-全色數的一個上界

*蔡學鵬，任佰通，馮苗苗

（新疆農業(yè)大學數理學院，新疆，烏魯木齊830052）

應用概率論中的Lovasz一般局部引理得出了圖的鄰點強可區(qū)別V-全色數的上界，證明了對階數不小于3且不含孤立邊的簡單圖的鄰點強可區(qū)別V-全色數不超過49△，△≥5。

Lovasz一般局部引理；鄰點強可區(qū)別全染色；鄰點強可區(qū)別V-全染色

0 引言

隨著計算機的飛速發(fā)展，信息化和數字化技術的不斷進步，許多實際問題的數學模型使離散型結構上的數字化技術得到了更多人的關注。圖的染色理論[1]作為離散數學的一個重要組成部分，自然得到了快速發(fā)展，因此受到了國際數學界與工程界越來越廣泛的重視。Noga Alon在2002年數學國際大會上作了“離散數學方法與挑戰(zhàn)”的大會報告后，圖的染色成為一個很活躍、很新穎的研究鄰域。1993年A.C.Burris在他的博士論文中提到了點可區(qū)別正常邊染色(也稱強邊染色)的概念[2]，此后P.N.Balister等人撰文[3]對該問題進行了深入的討論，有關許多深入的結果都在國際權威雜志上刊出。在無線通訊網絡中，為了防止網絡中不同的長點之間信號頻率的共振，必須保證不同站點之間擁有不同的通訊頻率，無線傳感器網絡中相鄰點通信沖突問題；交通運輸中危險品運輸的配送調度安全問題等，為了解決此問題，張忠輔教授首次提出了鄰點可區(qū)別正常邊染色[4]的概念，這一問題與點可區(qū)別邊染色的研究具有相同的難度，因此國內外專家對此問題作了大量研究。2004年張忠輔教授在鄰點可區(qū)別正常邊染色的基礎上提出了鄰點可區(qū)別全染色[5]的概念，2007年又提出了鄰點強可區(qū)別全染色[6]的概念。2010年程輝等在鄰點強可區(qū)別的基礎上提出了鄰點強可區(qū)別EI-全染色[7]和鄰點強可區(qū)別V-全染色[8]的概念。

圖染色理論中對于常見的特殊圖，如路圖、圈圖、星圖、扇圖和輪圖等，其染色數可以根據群染法、反證法和構造函數等方法得出確定的結果。對于一般圖而言，上述方法卻不再合理。而應用概率論中的Lovasz一般局部引理，可以很巧妙地得出一些不同類型的圖染色的上界，該方法在文獻[12-15]中有一些應用結果。本文在鄰點強可區(qū)別全染色的概念中，弱化其中的一個條件，即相鄰點可以染同色，從而得出了圖的鄰點強可區(qū)別V-全色數的上界。

1 預備知識

為的鄰點強可區(qū)別全色數。

為的鄰點強可區(qū)別V-全色數。該定義將定義1中的條件1)弱化了，即相鄰點可以染同色。

2 主要結論

1) 邊染色是正常的，既沒有兩條相鄰的邊染成同色；

2) 點和邊的染色是正常的，即任意一條邊與他的懸掛點染不同顏色；

3) 色集合是正常的，即任意相鄰兩點的色集合不同，這里的色集合為該點的顏色，與他關聯邊的顏色，以及與他相鄰點的顏色所組成的集合。下面將分三步完成該定理的證明。

第一步：定義以下三種類型的壞事件

如果壞事件1，2，3不發(fā)生的概率為正，即說明壞事件不發(fā)生是可能的，則稱上述條件是滿足的，即存在鄰點強可區(qū)別-全染色。下面計算每一個壞事件發(fā)生的概率：

由二項式定理知，

故

第二步：構造相關圖并計算相關事件數

表1 相關圖R

第三步：構造常數證明以下三個不等式成立

證明(4)式只需證：

同理對于(2)式有：

同理對于(3)式有：

綜上所述，取

[1] Bondy J A, Marty USR. Graph Theory with Application[M]. New York: The Macmillan Press Ltd, 1976.

[2] Burris A C, Schelp R H. Vertex-Distinguishing Proper Edge-Coloring[J]. J of Graph Theory, 1997, 26(2):73-82.

[3] Balister P N, Riordan O M, Schelp R H. Vertex‐distinguishing edge colorings of graphs[J]. Journal of graph theory, 2003, 42(2): 95-109.

[4] Zhang Z, Liu L, Wang J. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, 15(5): 623-626.

[5] Zhang Z, Chen X, Li J, et al. On adjacent- vertex-distinguishing total coloring of graphs[J]. Science in China Series A: Mathematics, 2005, 48(3): 289-299.

[6] 張忠輔,程輝,姚兵,等. 圖的鄰點強可區(qū)別全染色[J].中國科學(A輯),2007, 37(9):1073-1082.

[7] Cheng H, Wang Z. Adjacent vertex strongly distinguishing EI-total coloring of graphs[J].Shandong Univ.Nat.Sci.2010(3):289-299.

[8] 程輝,謝雁. 圖的鄰點強可區(qū)別VI-全染色[J].蘭州大學學報:自然科學版, 2010,46(6): 97-101.

[9] 安明強. 點可區(qū)別全色數的一個上界[J].天津科技大學學報, 2009, 24(5):68-70.

[10] Michael M, Bruce R. Graph coloring and the probabilistic method[M]. New York :Springer, 2002: 1329-1356.

[11] Alon N, Spencer J H. The Probabilistic Method[M]. New York:John Wiley &Sons, 1992.

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

[13] 強會英,李沐春,張忠輔,等. 距離限制下的點可區(qū)別全色數的一個上界[J].應用數學學報,2011, 34(3):554-559.

[14] 強會英,王洪申. 圖的鄰點強可區(qū)別全色數的一個上界[J].數學進展, 2013, 42(6):801-805.

[15] 崔俊峰. 圖的點可區(qū)別邊色數的一個上界[J].首都師范大學學報:自然科學版,2017, 38(1):6-8.

AN UPPER BOUND OF THE ADJACENT-VERTEX-STRONGLY-DISTINGUISHING V-TOTAL CHROMATIC NUMBERS OF GRAPHS

*CAI Xue-peng, REN Bai-tong, FENG Miao-miao

(College of Mathematics and Physics, Xinjiang Agricultural University, Urumqi, Xinjiang 830052, China)

An upper bound for adjacent-vertex-strongly-distinguishing V-total chromatic numbers is obtained by Lovasz local lemma of probability method. We show that adjacent vertex strongly distinguishing V-total chromatic numbers of graph G is not more than 49△for△≥5, where G is a simple graph with no isolated edge and the order not less than three.

Lovasz local lemma; the adjacent-vertex-strongly-distinguishing total coloring; the adjacent-vertex-strongly-distinguishing V-total coloring

1674-8085(2018)03-0005-04

O157.5

A

10.3969/j.issn.1674-8085.2018.03.002

2018-03-09；

2018-04-16

*蔡學鵬(1991-)，男，甘肅武威人，助教，碩士，主要從事圖與網絡優(yōu)化研究(Email:522916724@qq.com);

任佰通(1997-)，男，重慶人，新疆農業(yè)大學數理學院本科生(Email:3212989741@qq.com);

馮苗苗(1999-)，女，重慶人，新疆農業(yè)大學數理學院本科生(Email:2955398005@qq.com).