图的2-强点可区别全色数的上界*

贾泽乐 王鸿杰 李沐春

(兰州交通大学应用数学研究所,甘肃 兰州 730070)

1 引言及主要结论

本文主要考虑不含孤立边的简单连通图.设G=(V,E)表示顶点集为V,边集为E的简单图. 用d和n分别表示图G的最大度与阶数.Kn表示n阶完全图,K3-free图指不包含K3的图.

2017年,Wen等[8]经过对强染色的研究,引入了图的r-强点可区别全染色,并分别给出了K3-free图的1-强点可区别全色数,树图的2-强点可区别全色数与3-强点可区别全色数的一个上界.下面给出r-强点可区别全染色的概念：

定义1[8]对于阶数不小于3的简单连通图G,设k为正整数,令映射f：V(G)∪E(G)→{1,2,…,k}.若f满足下面条件：

(1)对∀uv,uw∈E(G),且v≠w,有f(uv)≠f(uw)；

(2)对∀uv∈E(G)，有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv)；

(3)对∀u,v∈V(G), 当1≤d(u,v)≤r时, 都有C(u)≠C(v).

则称f为图G的r-强点可区别全染色,其中C(u)={f(u)}∪{f(v)}∪{f(uv)|uv∈E(G)}.简记作图G的k-r-SVDTC,并称

χr-svdt(G)=min{k|G具有k-r-SVDTC}

为图G的距离为r-强点可区别全色数.

注1 根据定义1可知,任意图G可r-强点可区别全染色的必要条件是图G不含有孤立边且最大度d≥2.

特别地, 当r=1时,即为图的1-强点可区别全染色(邻点强可区别全染色);当r为图的直径时, 即为图的点强可区别全染色;r=2时,成为图的2-强点可区别全染色,所需最少颜色数称为2-强点可区别全色数. 本文应用概率方法中的Lovász局部引理得到了图G的2-强点可区别全色数的上界.

定理1对不含孤立边的简单图G,则χ2-svdt(G)≤35d2.

2 定理1的证明

为了证明定理1,首先给出Lovász局部引理,它将在后面的证明中起到重要作用.

下面给出定理1的具体证明过程：

定理1证明：设f∶E(G)∪V(G)→{1,2,…,c}是图G的随机全染色,并且对任意边e∈E(G),f(e)是{1,2,…,c}随机均匀的边染色且对任意u,v∈V(G),f(u),f(v)是{1,2,…,c}随机均匀的点染色,其中c=kd2(k为正整数). 为了保证图G是2-强点可区别全染色,需满足以下条件：

(1)正常全染色——任意两条相邻边不能染同色;任意两个相邻点不能染同色；点和关联边不能染同色;

(2)2-强点可区别——任意两个距离不超过2的点的色集合均不同.

第一步,定义如下坏事件

(1)对每一对相邻的点u,v∈V(G),令EA表示u和v染相同颜色的事件;

(2)对每一对相邻的边e1,e2∈E(G),令EB表示e1和e2染同种颜色的事件;

(3)对任意一条边e=uv∈E(G),令EC表示e与关联点u或v染同色的事件;

(4)对任意两点u,v∈V(G),其中1≤d(u,v)≤2,令ED表示点u与v的色集合满足C(u)=C(v)的事件.

第二步, 计算坏事件发生的概率

若事件ED发生，指任意两点u和v在距离为2的条件下，满足色集合C(u)=C(v)，而使得C(u)=C(v)可能值的总数为：

因此，概率为

第三步, 计算相关事件数

首先构造图D,其结点为4种类型的所有事件,其中两个结点EX和EY相关, 当且仅当X和Y包含一个公共元素.因为每个事件EX的发生,仅依赖于X的元素,所以D是上述事件的相关图．

对上述坏事件的相关数进行简要分析,如下：

根据上面的相关数分析,得到了如下的关系关联矩阵.

第四步,构造常数证明不等式.

应用Lovász局部引理证明坏事件不发生的概率为正,即说明2-强点可区别全染色是存在的.因此,只需证明以下四个不等式成立：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

从上面(5)至(8)式可以得到,只有当c,d满足一定条件时,不等式才成立.我们注意到当d≥2时,18d2+32d+2≥{30d-12,25d+16,38d-8}.因此,(5)—(8)成立只需要(8)成立即可.此时,令c=kd2(k>0),由(8)可知,

因此，当d≥2,k≥35时,不等式

成立.

综上所述，当d=Δ(G)≥2时,对简单图G,有χ2-svdt(G)≤35d2.