邊替換圖的鄰和可區(qū)別全染色

常景智,楊 超,姚 兵

(1.上海工程技術(shù)大學(xué) 數(shù)理與統(tǒng)計學(xué)院,智能計算與應(yīng)用統(tǒng)計研究中心,上海 201620; 2.西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,蘭州 730070)

1 引言與預(yù)備知識

圖的可區(qū)別染色問題是圖論中的研究熱點[1-2],目前已廣泛應(yīng)用于計算機(jī)科學(xué)、生命科學(xué)以及網(wǎng)絡(luò)通信等領(lǐng)域.近年來,關(guān)于把點和邊所染顏色相加的可區(qū)別染色問題也得到廣泛關(guān)注.Karoński等[3]研究了圖的鄰和可區(qū)別邊染色,提出了1-2-3猜想.

猜想1(1-2-3猜想)[3]設(shè)G為一個階數(shù)至少為3的簡單連通圖,則gndiΣ(G)≤3.

Kalkowski等[4]證明了階數(shù)至少為3的簡單連通圖的鄰和可區(qū)別邊色數(shù)不超過5.關(guān)于鄰和可區(qū)別邊染色的研究目前已有很多結(jié)果[5-8].Przybyo等[9]提出了圖的鄰和可區(qū)別全染色的概念,并給出了1-2猜想,證明了該猜想對3-點可染色圖、完全圖和四正則圖均成立,且任意簡單連通圖的鄰和可區(qū)別全色數(shù)不超過11.Kalkowski[10]得到了任意圖的鄰和可區(qū)別全色數(shù)不超過3.程銀萬等[11]證明了Halin圖的鄰和可區(qū)別全色數(shù)不超過2.

猜想2(1-2猜想)[9]設(shè)G為一個簡單連通圖,則tgndiΣ(G)≤2.

設(shè)G和T是兩個簡單圖,i和j為T中的兩個固定頂點,滿足T-i和T-j同構(gòu).用T替換圖G的每條邊e=(u,v),使得i=u,j=v,所得圖稱為邊替換圖[12],記為G[T].由定義可知,當(dāng)T=P3,即T為3個頂點的路且i和j為P3的兩個端點時,G[P3]為圖G的剖分圖,記為S(G); 當(dāng)T=C3,即T為3個頂點的圈且i和j為C3的兩個端點時,G[C3]為圖G的三角擴(kuò)展圖,記為R(G).

設(shè)圖G=(V(G),E(G))是一個無向簡單圖,若點集S?V(G),且當(dāng)去掉S后,剩余的子圖G-S中不含任何圈,則S稱為圖G的一個消圈集,同時min{|S||S是圖G的消圈集}稱為圖G的消圈數(shù),記為(G),且此時的消……