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

2013-08-13刘德刚

黑龙江工程学院学报 2013年1期

刘德刚

（黑龙江工程学院数学系，黑龙江哈尔滨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。