最大度不大于5的圖的2距離列表染色

李祿佳 孫明皓 孫 磊

( 山東師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,250358,濟(jì)南 )

1 引 言

在無(wú)線通訊網(wǎng)絡(luò)信道分配問(wèn)題中,將網(wǎng)絡(luò)抽象為圖建立數(shù)學(xué)模型,其中距離小于等于2的點(diǎn)對(duì)應(yīng)的網(wǎng)絡(luò)節(jié)點(diǎn)會(huì)有信道約束.這里所研究的信道分配問(wèn)題是研究如何分配信道使?jié)M足信道約束的網(wǎng)絡(luò)節(jié)點(diǎn)保持信道分離且使用最少的信道數(shù)目使整個(gè)網(wǎng)絡(luò)的干擾達(dá)到最小或者沒(méi)有干擾.通過(guò)建立數(shù)學(xué)模型,可將信道分配問(wèn)題轉(zhuǎn)化為在網(wǎng)絡(luò)對(duì)應(yīng)的圖中給距離小于等于2的點(diǎn)分配不同顏色的2距離染色問(wèn)題.如果每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)有特定信道可選,就可將此問(wèn)題進(jìn)一步轉(zhuǎn)化為圖的2距離列表染色問(wèn)題[1].

本文只研究無(wú)向有限簡(jiǎn)單圖.d(v)表示頂點(diǎn)v在圖G中的度數(shù),若d(v)=k(或d(v)≥k,d(v)≤k),則稱(chēng)點(diǎn)v為一個(gè)k-點(diǎn)(或k+-點(diǎn),或k--點(diǎn)).Δ(G)表示圖G的最大度.l-段是路P=vx1x2…xlu,滿足d(xi)=2，i=1,2,…,l,且d(u)≥3,d(v)≥3.懸掛邊表示一個(gè)1-點(diǎn)與關(guān)聯(lián)此點(diǎn)的一條邊.

文中所出現(xiàn)的圖,實(shí)心點(diǎn)表示此點(diǎn)的度數(shù)已知,白點(diǎn)表示此點(diǎn)的度數(shù)未知.

文中未加說(shuō)明的符號(hào)和術(shù)語(yǔ)與文獻(xiàn)[2]一致.

2 研究概況

關(guān)于圖的2距離染色問(wèn)題, Wegner從1977年開(kāi)始研究,并在文獻(xiàn)[3]中提出了如下猜想1.

這個(gè)重要的猜想目前還沒(méi)有得到完全證明.但部分結(jié)果已經(jīng)得到證明，比如對(duì)于Δ=3的平面圖, Thomassen在文獻(xiàn)[4]中證明了上述猜想成立.目前對(duì)于圖的2距離染色數(shù)的上界,有很多結(jié)論是關(guān)于平面圖的, Molloy等人在文獻(xiàn)[5]中證明了下面的定理1.

將研究對(duì)象限制到滿足某種約束條件的圖類(lèi)中,比如對(duì)平面圖的圍長(zhǎng)加以限制,會(huì)得到更好的對(duì)于平面圖的2距離染色數(shù)的上界, Borodin等人在文獻(xiàn)[6]中證明了下面的定理2.

定理2[6]給定g(G)≥6且Δ(G)≥18的平面圖G,有χ2(G)≤Δ(G)+2.

隨著研究的深入,人們不再局限于圖的2距離染色,開(kāi)始研究條件更加嚴(yán)苛的圖的2距離列表染色.Borodin等人在文獻(xiàn)[7]中將定理2的結(jié)果推廣到2距離列表染色,得到了下面的定理3.

Bonamy等人在文獻(xiàn)[8]中將定理3的結(jié)果做了改進(jìn),將最大度的條件放寬,得到了下面的定理4.

對(duì)于一般圖的2距離染色問(wèn)題,近年, Cranston等人研究了在最大度與最大平均度條件下的一般圖的2距離染色問(wèn)題,并在文獻(xiàn)[1]中得到了下面的定理5.

定理5[1]對(duì)于圖G,有如下結(jié)論成立：

嚴(yán)曉燕在文獻(xiàn)[9]中將定理5中的結(jié)果做了改進(jìn),得到了下面的定理6.

卜月華等人在文獻(xiàn)[10]中進(jìn)一步討論了有最大平均度限制的最大度不大于5的一般圖的2距離列表染色問(wèn)題,并得到了下面的定理7.

定理7[10]對(duì)于圖G,有如下結(jié)論成立:

3 主要結(jié)果及證明

在前人研究的基礎(chǔ)上，本文主要得到了下面的定理8.

下面在3.1節(jié)中探討最小反例的結(jié)構(gòu)性質(zhì)，在3.2節(jié)中給出定理8的完整證明.

(C1) 4-段；

(C2) 一個(gè)端點(diǎn)為4--點(diǎn)的3-段；

(C3) 一個(gè)端點(diǎn)為3-點(diǎn),另一個(gè)端點(diǎn)為4--點(diǎn)的2-段；

(C4) 當(dāng)4|i時(shí)d(vi)=5,其它點(diǎn)d(vi)=2的4l-圈v1v2…v4l；

(C5) 當(dāng)3|i時(shí)d(vi)=4,其它點(diǎn)d(vi)=2的3l-圈v1v2…v3l；

(C6) 由端點(diǎn)都是3-點(diǎn)的1-段組成的圈,且至少一個(gè)3-點(diǎn)關(guān)聯(lián)另一個(gè)端點(diǎn)也是3-點(diǎn)的1-段(圖1)；

圖1 可約構(gòu)型(C6)

(C7) 關(guān)聯(lián)兩條2-段(與點(diǎn)v相鄰的2-點(diǎn)分別為點(diǎn)u1,u2)且相鄰一個(gè)3--點(diǎn)(點(diǎn)u3)的3-點(diǎn)(點(diǎn)v).

(C8) 關(guān)聯(lián)一條2-段和兩條1-段且其中一條1-段的另一端點(diǎn)為4--點(diǎn)的3-點(diǎn)(圖2)；

圖2 可約構(gòu)型(C8)

證在圖G′即G-N[v]中,若d(wi)=3(i=1,2)且點(diǎn)wi(i=1,2)的鄰點(diǎn)中有5-點(diǎn),則對(duì)點(diǎn)wi(i=1,2)增加一條懸掛邊.此時(shí)可使圖G′滿足每個(gè)5-點(diǎn)至少相鄰一個(gè)3+-點(diǎn)并且|V(G′)|+|E(G′)|≤|V(G)|+|E(G)|-4-3+4<|V(G)|+|E(G)|.因?yàn)閳DG是極小反例,但圖G′的點(diǎn)數(shù)加邊數(shù)之和小于圖G,所以可以將圖G′進(jìn)行染色.染色完成后,再將新增加的懸掛邊去掉.接下來(lái),在此基礎(chǔ)上對(duì)圖G進(jìn)行染色.首先,點(diǎn)u1的可用色數(shù)至少為6-5=1,將點(diǎn)u1進(jìn)行染色.之后,點(diǎn)u2的可用色數(shù)至少為6-4-1=1,將點(diǎn)u2進(jìn)行染色.點(diǎn)v的可用色數(shù)至少為6-2-2-1=1,將點(diǎn)v進(jìn)行染色.最后,點(diǎn)u3的可用色數(shù)至少為6-2-3=1,所以將點(diǎn)u3進(jìn)行染色.此時(shí),能夠?qū)DG染好.

由文獻(xiàn)[1]中定理4的證明可知,每條3-段都可視為由它的一個(gè)端點(diǎn)發(fā)起,且每個(gè)5-點(diǎn)至多發(fā)起一條3-段.端點(diǎn)都是4-點(diǎn)的2-段都可視為由它的一個(gè)端點(diǎn)發(fā)起,且每個(gè)4-點(diǎn)至多發(fā)起一條2-段.端點(diǎn)是3-點(diǎn)的1-段都可視為由它的一個(gè)端點(diǎn)發(fā)起,且每個(gè)3-點(diǎn)至多發(fā)起一條1-段.

3.2定理8的證明

對(duì)于任意v∈V(G)構(gòu)造初始權(quán)函數(shù)為ω(v)=d(v),可得

(1)

本文所提到的給l-段轉(zhuǎn)權(quán)值,都是指給l-段上的所有2-點(diǎn)所轉(zhuǎn)的權(quán)值總和.所轉(zhuǎn)的權(quán)值總和之后會(huì)由段上的2-點(diǎn)均分.

定義權(quán)轉(zhuǎn)移規(guī)則如下：

下面分4種類(lèi)型檢查每個(gè)頂點(diǎn)的新權(quán)值.

1)d(v)=5.由定理8的條件及(C1)知,5-點(diǎn)最多關(guān)聯(lián)4條l-段(l=1,2,3),所以由(R1)得

2)d(v)=4.由(C1),(C2)知，4-點(diǎn)最多關(guān)聯(lián)4條l-段(l=1,2),所以由(R2)得

3)d(v)=3.由(C7)知,點(diǎn)v最多關(guān)聯(lián)兩條2-段,考慮它關(guān)聯(lián)2-段條數(shù)的下述3種情況.

① 點(diǎn)v關(guān)聯(lián)兩條2-段，由(C7)知，此時(shí)點(diǎn)v相鄰一個(gè)4+-點(diǎn).由(R3)得

4)d(v)=2.對(duì)于2-點(diǎn),考慮它在段上的下述3種情況.

① 2-點(diǎn)在3-段上.由(C2)知,每條3-段的端點(diǎn)都是5-點(diǎn),且由一個(gè)端點(diǎn)發(fā)起,由(R1)得

② 2-點(diǎn)在2-段上. 由C3知,2-段的端點(diǎn)只有以下2種：一個(gè)端點(diǎn)是3-點(diǎn),另一個(gè)端點(diǎn)是5-點(diǎn)或者都是4+-點(diǎn).

(2)

這與(1)式矛盾,從而定理8得證.