图的距离不大于2的点可区别的边色数的一个新的上界

刘德刚

（黑龙江工程学院 数学系，黑龙江 哈尔滨150050）

图的染色问题在图和组合学领域具有重大的理论意义和实际价值，其基本问题是确定各种类型的染色方法的色数。以前人们往往采用组合方法得到许多结果［1－2］，1974年 Erdös在Ramsey数r（k，k）≥的证明中首次引入概率方法。2002年，Alon在国际数学家大会上作了关于离散数学方法与挑战的报告，图的研究概率方法以其有效性和新颖性在图论届受到广泛关注和利用。目前用概率方法得到的重要结果有：Alon［3］等提出图的无圈边染色的色数的一个上界；文献［4］简单图G，Δ≥1020，χas（G）＜Δ＋300；2006年，张忠辅等人［5］提出图的距离不大于β的任意两点可区别边染色，也可以称为图的α－D（β）－点可区别的边染色；文献［6］用图的概率方法中的一阶矩原理和Markov不等式得到β＝2时，图的D（β）－点可区别的边色数的一个上界，本文用图论概率方法中的一阶矩原理和Markov不等式，对文献［6］的方法改造得到图的距离不大于2的点可区别的边色数的一个新的上界，结果好于文献［6］。

定义1［5］对于阶数不小于3的连通图G（V，E），设α、β为正整数，令染色映射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（β）－点可区别的边染色，简记为α－D（β）－VDPEC，对一个图进行α－D（β）－点可区别边染色时所需要的最小α称为图G的D（β）－点可区别边染色的边色数，记为（G），其中d（u，v）表示2个顶点u、v之间的最短距离。当β＝1时，图的D（β）点可区别的边染色就是邻点可区别边染色，当β＝diam（G）（图的直径）时，图的D（β）点可区别边染色就是点可区别边染色。本文仅讨论β＝2时，图的D（β）－点可区别边染色的色数的一个改进的上界，考虑的图为有限的、无向的、简单的、连通的图。

定义2［7］随 机 变 量 的 数 学 期 望 是E（X）＝； 数 学 期 望 的 线 性 性

引理1［7］（Markov不等式）对于任意的非负随机变量X，有。如果X是正整数并且E（X）＜1，那么＝E（X），也即Pr（X≥0）≤E（X）。

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

引理4［9］对于最大度为d，有n个顶点的简单图G，d≥3，有nd（d－1），本文未加说明的术语参阅文献［8］。

定理1 对最大度Δ（G）＝d，d≥3，n个顶点的简 单 图 G （V，E ） 有 χ′2－vd（G ） ≤

为此，定义如下示性变量：

对每一个相邻的边e、g，令

对每一对相邻的顶点u、v，令

对边长为2的路uevfw，令

现在只要能证明Pr（X＝0，Y＝0，Z＝0）＞0，那么，必存在图G的距离不大于2的点可区别的边染色。根据引理3，只要证明

即只要证明

然而，根据Markor不等式

所以，只需证明

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

根据期望的线性有

现在，要证明

必成立。

因此，对最大度Δ（G）＝d，d≥3，n个顶点的简单图G（V，E）有

总之，定理1的上界要小于文献［6］的结果，即引理4：对于最大度为d，有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］张忠辅，李敬文，陈祥恩，等.图的距离不大于β的任意两 点 可 区 别 的 边 染 色 ［J］.数 学 学 报，2006，49（3）：703－708.

［6］田京京，邓方安，张忠辅.图的距离不大于2的点可区别边色数的一个上界［J］.数学的实践与认识，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.