圖的2-強(qiáng)點(diǎn)可區(qū)別全色數(shù)的上界*

賈澤樂 王鴻杰 李沐春

(蘭州交通大學(xué)應(yīng)用數(shù)學(xué)研究所,甘肅 蘭州 730070)

1 引言及主要結(jié)論

本文主要考慮不含孤立邊的簡單連通圖.設(shè)G=(V,E)表示頂點(diǎn)集為V,邊集為E的簡單圖. 用d和n分別表示圖G的最大度與階數(shù).Kn表示n階完全圖,K3-free圖指不包含K3的圖.

2017年,Wen等[8]經(jīng)過對強(qiáng)染色的研究,引入了圖的r-強(qiáng)點(diǎn)可區(qū)別全染色,并分別給出了K3-free圖的1-強(qiáng)點(diǎn)可區(qū)別全色數(shù),樹圖的2-強(qiáng)點(diǎn)可區(qū)別全色數(shù)與3-強(qiáng)點(diǎn)可區(qū)別全色數(shù)的一個上界.下面給出r-強(qiáng)點(diǎn)可區(qū)別全染色的概念：

定義1[8]對于階數(shù)不小于3的簡單連通圖G,設(shè)k為正整數(shù),令映射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), 當(dāng)1≤d(u,v)≤r時, 都有C(u)≠C(v).

則稱f為圖G的r-強(qiáng)點(diǎn)可區(qū)別全染色,其中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-強(qiáng)點(diǎn)可區(qū)別全色數(shù).

注1 根據(jù)定義1可知,任意圖G可r-強(qiáng)點(diǎn)可區(qū)別全染色的必要條件是圖G不含有孤立邊且最大度d≥2.

特別地, 當(dāng)r=1時,即為圖的1-強(qiáng)點(diǎn)可區(qū)別全染色(鄰點(diǎn)強(qiáng)可區(qū)別全染色);當(dāng)r為圖的直徑時, 即為圖的點(diǎn)強(qiáng)可區(qū)別全染色;r=2時,成為圖的2-強(qiáng)點(diǎn)可區(qū)別全染色,所需最少顏色數(shù)稱為2-強(qiáng)點(diǎn)可區(qū)別全色數(shù). 本文應(yīng)用概率方法中的Lovász局部引理得到了圖G的2-強(qiáng)點(diǎn)可區(qū)別全色數(shù)的上界.

定理1對不含孤立邊的簡單圖G,則χ2-svdt(G)≤35d2.

2 定理1的證明

為了證明定理1,首先給出Lovász局部引理,它將在后面的證明中起到重要作用.

下面給出定理1的具體證明過程：

定理1證明：設(shè)f∶E(G)∪V(G)→{1,2,…,c}是圖G的隨機(jī)全染色,并且對任意邊e∈E(G),f(e)是{1,2,…,c}隨機(jī)均勻的邊染色且對任意u,v∈V(G),f(u),f(v)是{1,2,…,c}隨機(jī)均勻的點(diǎn)染色,其中c=kd2(k為正整數(shù)). 為了保證圖G是2-強(qiáng)點(diǎn)可區(qū)別全染色,需滿足以下條件：

(1)正常全染色——任意兩條相鄰邊不能染同色;任意兩個相鄰點(diǎn)不能染同色；點(diǎn)和關(guān)聯(lián)邊不能染同色;

(2)2-強(qiáng)點(diǎn)可區(qū)別——任意兩個距離不超過2的點(diǎn)的色集合均不同.

第一步,定義如下壞事件

(1)對每一對相鄰的點(diǎn)u,v∈V(G),令EA表示u和v染相同顏色的事件;

(2)對每一對相鄰的邊e1,e2∈E(G),令EB表示e1和e2染同種顏色的事件;

(3)對任意一條邊e=uv∈E(G),令EC表示e與關(guān)聯(lián)點(diǎn)u或v染同色的事件;

(4)對任意兩點(diǎn)u,v∈V(G),其中1≤d(u,v)≤2,令ED表示點(diǎn)u與v的色集合滿足C(u)=C(v)的事件.

第二步, 計(jì)算壞事件發(fā)生的概率

若事件ED發(fā)生，指任意兩點(diǎn)u和v在距離為2的條件下，滿足色集合C(u)=C(v)，而使得C(u)=C(v)可能值的總數(shù)為：

因此，概率為

第三步, 計(jì)算相關(guān)事件數(shù)

首先構(gòu)造圖D,其結(jié)點(diǎn)為4種類型的所有事件,其中兩個結(jié)點(diǎn)EX和EY相關(guān), 當(dāng)且僅當(dāng)X和Y包含一個公共元素.因?yàn)槊總€事件EX的發(fā)生,僅依賴于X的元素,所以D是上述事件的相關(guān)圖．

對上述壞事件的相關(guān)數(shù)進(jìn)行簡要分析,如下：

根據(jù)上面的相關(guān)數(shù)分析,得到了如下的關(guān)系關(guān)聯(lián)矩陣.

第四步,構(gòu)造常數(shù)證明不等式.

應(yīng)用Lovász局部引理證明壞事件不發(fā)生的概率為正,即說明2-強(qiáng)點(diǎn)可區(qū)別全染色是存在的.因此,只需證明以下四個不等式成立：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

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

因此，當(dāng)d≥2,k≥35時,不等式

成立.

綜上所述，當(dāng)d=Δ(G)≥2時,對簡單圖G,有χ2-svdt(G)≤35d2.