圖的距離不大于2的點(diǎn)可區(qū)別的邊色數(shù)的一個新的上界

劉德剛

（黑龍江工程學(xué)院 數(shù)學(xué)系，黑龍江 哈爾濱150050）

圖的染色問題在圖和組合學(xué)領(lǐng)域具有重大的理論意義和實際價值，其基本問題是確定各種類型的染色方法的色數(shù)。以前人們往往采用組合方法得到許多結(jié)果［1－2］，1974年 Erd?s在Ramsey數(shù)r（k，k）≥的證明中首次引入概率方法。2002年，Alon在國際數(shù)學(xué)家大會上作了關(guān)于離散數(shù)學(xué)方法與挑戰(zhàn)的報告，圖的研究概率方法以其有效性和新穎性在圖論屆受到廣泛關(guān)注和利用。目前用概率方法得到的重要結(jié)果有：Alon［3］等提出圖的無圈邊染色的色數(shù)的一個上界；文獻(xiàn)［4］簡單圖G，Δ≥1020，χas（G）＜Δ＋300；2006年，張忠輔等人［5］提出圖的距離不大于β的任意兩點(diǎn)可區(qū)別邊染色，也可以稱為圖的α－D（β）－點(diǎn)可區(qū)別的邊染色；文獻(xiàn)［6］用圖的概率方法中的一階矩原理和Markov不等式得到β＝2時，圖的D（β）－點(diǎn)可區(qū)別的邊色數(shù)的一個上界，本文用圖論概率方法中的一階矩原理和Markov不等式，對文獻(xiàn)［6］的方法改造得到圖的距離不大于2的點(diǎn)可區(qū)別的邊色數(shù)的一個新的上界，結(jié)果好于文獻(xiàn)［6］。

定義1［5］對于階數(shù)不小于3的連通圖G（V，E），設(shè)α、β為正整數(shù)，令染色映射f：E→｛1，2，…，α｝，如果?u，v∈V（G），1≤d（u，v）≤β，有C（u）≠C（v），C（u）＝ ｛f（ux）：ux∈E（G）｝，則稱f為圖G的一個α－D（β）－點(diǎn)可區(qū)別的邊染色，簡記為α－D（β）－VDPEC，對一個圖進(jìn)行α－D（β）－點(diǎn)可區(qū)別邊染色時所需要的最小α稱為圖G的D（β）－點(diǎn)可區(qū)別邊染色的邊色數(shù)，記為（G），其中d（u，v）表示2個頂點(diǎn)u、v之間的最短距離。當(dāng)β＝1時，圖的D（β）點(diǎn)可區(qū)別的邊染色就是鄰點(diǎn)可區(qū)別邊染色，當(dāng)β＝diam（G）（圖的直徑）時，圖的D（β）點(diǎn)可區(qū)別邊染色就是點(diǎn)可區(qū)別邊染色。本文僅討論β＝2時，圖的D（β）－點(diǎn)可區(qū)別邊染色的色數(shù)的一個改進(jìn)的上界，考慮的圖為有限的、無向的、簡單的、連通的圖。

定義2［7］隨 機(jī) 變 量 的 數(shù) 學(xué) 期 望 是E（X）＝； 數(shù) 學(xué) 期 望 的 線 性 性

引理1［7］（Markov不等式）對于任意的非負(fù)隨機(jī)變量X，有。如果X是正整數(shù)并且E（X）＜1，那么＝E（X），也即Pr（X≥0）≤E（X）。

引理2［7］（一階矩原理）如果E（X）≤t，那么Pr（X≤t）≥0。

引理4［9］對于最大度為d，有n個頂點(diǎn)的簡單圖G，d≥3，有nd（d－1），本文未加說明的術(shù)語參閱文獻(xiàn)［8］。

定理1 對最大度Δ（G）＝d，d≥3，n個頂點(diǎn)的簡 單 圖 G （V，E ） 有 χ′2－vd（G ） ≤

為此，定義如下示性變量：

對每一個相鄰的邊e、g，令

對每一對相鄰的頂點(diǎn)u、v，令

對邊長為2的路uevfw，令

現(xiàn)在只要能證明Pr（X＝0，Y＝0，Z＝0）＞0，那么，必存在圖G的距離不大于2的點(diǎn)可區(qū)別的邊染色。根據(jù)引理3，只要證明

即只要證明

然而，根據(jù)Markor不等式

所以，只需證明

事實上，可以計算及放大E（X）、E（Y）、E（Z），如下：

根據(jù)期望的線性有

現(xiàn)在，要證明

必成立。

因此，對最大度Δ（G）＝d，d≥3，n個頂點(diǎn)的簡單圖G（V，E）有

總之，定理1的上界要小于文獻(xiàn)［6］的結(jié)果，即引理4：對于最大度為d，有n個頂點(diǎn)的簡單圖G，d≥3，有（G）nd（d－1）。

［1］Wang Weifan.Equitable total coloring graphs with maximum dgree 3［J］.Graphs and Combinatorics，2002，18：677－685.

［2］Bazgan C，Harkat－Benhamdine A ，Li Hao，et al.On the Vertex－distinguishing Proper Edge－colorings of Graphs［J］.J Combin Theory（Ser.B），1999，75：288－301.

［3］Alon N.sadakov B，Zaks A.Acyclic edge coloring of graphs［J］.Journal of Graph Theory，2001，37：157－167.

［4］Hatami H.Δ＋300is bound on the adiacent vertex distinguishing edge chromatic number graphs［J］.Journal of Combinatorial Theory，2003，36（2）：135－139.

［5］張忠輔，李敬文，陳祥恩，等.圖的距離不大于β的任意兩 點(diǎn) 可 區(qū) 別 的 邊 染 色 ［J］.數(shù) 學(xué) 學(xué) 報，2006，49（3）：703－708.

［6］田京京，鄧方安，張忠輔.圖的距離不大于2的點(diǎn)可區(qū)別邊色數(shù)的一個上界［J］.數(shù)學(xué)的實踐與認(rèn)識，2009，39（18）：195－198.

［7］Michael M ，Bruce R.Graph coloring and Probabilistic Method［M］.Springer，2002.

［8］Spncer A N，Alon N.The Probabilistic Method［M］.［出版社不詳］，1992.

［9］Bondy J A，Merty U S R.Graph Theory with Applications［M］.New York：The Macmillian Press Ltd，1976.