圖的帶有路長(zhǎng)限制的點(diǎn)染色研究.pdf

1、G的點(diǎn)染色是G的頂點(diǎn)集的一個(gè)剖分.如果G的頂點(diǎn)集V可以剖分成k個(gè)部分V1,V2,…,Vk,使得k∪i=1Vi=V,Vi∩Vj=0對(duì)任意i≠i成立,且對(duì)任意1≤i≤k,G[Vi]滿足某種特定要求.若V1,V2,…,Vk是點(diǎn)獨(dú)立集,則稱這種染色是正常染色；若V1,V2,…,Vk不是點(diǎn)獨(dú)立集,則稱這種染色是非正常染色.如果圖G可以用k種顏色正常染色,則稱G為k可染的.令x(G)=min{k|G是k色可染的},稱χ(G)為圖G的點(diǎn)色數(shù),有時(shí)簡(jiǎn)稱

2、為色數(shù).論文第一章主要介紹了一些基本概念和符號(hào),闡述了圖的非正常點(diǎn)染色的歷史及發(fā)展,本文中未加說(shuō)明的術(shù)語(yǔ)和符號(hào)參見(jiàn)文獻(xiàn)[1].
　　定義1.2.1令G=(V,E)是一個(gè)圖,圖G的一種退化染色是把圖G的頂點(diǎn)剖分成k個(gè)部分V1,V2,…,Vk,使得k∪i=1Vi=V,Vi∩Vj=0對(duì)任意i≠i成立,且對(duì)任意1≤i≤k,G[K]中所有頂點(diǎn)的度數(shù)不超過(guò)di,則稱圖G是(d1,d2,…,dk)可染的.
　　這種非正常染色是對(duì)每個(gè)色類的

3、點(diǎn)導(dǎo)出子圖中頂點(diǎn)的度數(shù)做限制.1976年,Steinberg提出了如下猜想.
　　猜想1.2.1[2]不含4-圈和5-圈的平面圖是三色可染的,即(0,0,0)-可染的.
　　為了證明這一猜想,一些學(xué)者將染色推廣到了退化染色,主要有以下結(jié)果.
　　定理1.2.3 (1)[14]若圖G為平面圖,且不含相交三角形和5-圈,則圖G是(1,1,0)-可染的.
　　(2)[15]若圖G為平面圖,且不含相交三角形和5-圈,則圖

4、G是(2,0,0)-可染的.
　　(3)[16]若圖G為平面圖,且不含鄰接三角形和5-圈,則圖G是(1,1,1)-可染的.
　　(4)[17]若圖G為平面圖,且不含4-圈和5-圈,則圖G是(1,1,0)-可染的.
　　(5)[18]若圖G為平面圖,且不含4-圈和5-圈,則圖G是(3,0,0)-可染的.
　　(6)[19]圖G為平面圖,且不含4-圈和6-圈,則圖G是(1,1,0)-可染的.
　　(7)[20]

5、若圖G為平面圖,且不含4-圈和6-圈,則圖G是(2,0,0)-可染的.
　　當(dāng)G[Vi]給定其它限制時(shí),可以導(dǎo)出圖G的幾類其它染色.例如定義1.2.2定義的這種非正常染色.
　　定義1.2.2 令G=(V,E)是一個(gè)圖,如果圖G的頂點(diǎn)可以剖分成k個(gè)部分V1,V2,…,Vk,使得k∪i=1Vi=V,Vi∩Vj=0對(duì)任意i≠i成立,且對(duì)任意1≤i≤k,G[Vi]為森林,滿足上述條件的k的最小值稱為圖G的點(diǎn)蔭度,記作va(G).<

6、br>　　孫磊老師在2015年提出了一種新的非正常染色,這種染色規(guī)定G[Vi]不含長(zhǎng)度超過(guò)l(l≥0)的路Pl,這里l指路P的邊數(shù),具體定義如下.
　　定義1.2.3如果圖G的頂點(diǎn)可以剖分成k個(gè)部分V1,V2,…,Vk,使得k∪i=1Vi= V,Vi∩Vj=0對(duì)任意i≠j成立,且Vi的導(dǎo)出子圖G[Vi]不含長(zhǎng)度超過(guò)l(l≥0)的路Bl,其中1≤i≤k,則稱圖G有一個(gè)Pl-染色(稱作是Pl-可染的).使得圖G有不含長(zhǎng)度超過(guò)l(l≥0

7、)的路Pl染色的最小剖分?jǐn)?shù)k叫做圖G的Pl-染色數(shù),記作xpl(G).
　　論文第二章主要研究了簡(jiǎn)單圖的P2-染色,尤其是具有低最大度圖的P2-染色,分別給出了△(G)≤3及△(G)≤4時(shí),圖G的P2-色數(shù)的上界,并且證明了這個(gè)上界是緊的.
　　定理2.1.1對(duì)任意簡(jiǎn)單圖G,若△(G)≤3,則χρ2(G)≤2.
　　這個(gè)色數(shù)上界是緊的,因?yàn)槿我庖粭l路長(zhǎng)超過(guò)2的路都必須至少用兩個(gè)顏色來(lái)染.
　　定理2.1.1’對(duì)任

8、意簡(jiǎn)單圖G,若△(G)≤3,可在多項(xiàng)式時(shí)間內(nèi)找到一個(gè)圖G的色數(shù)至多為2的P2—染色.
　　定理2.2.1對(duì)任意簡(jiǎn)單圖G,若△(G)≤4,則χρ2(G)≤3.
　　定理2.2.1’對(duì)任意簡(jiǎn)單圖G,若△(G)≤4,可在多項(xiàng)式時(shí)間內(nèi)找到一個(gè)圖G的色數(shù)至多為3的P2-染色.
　　這個(gè)色數(shù)上界是緊的,比如如下定義的圖G:
　　V(G)={vij|i=1,2,3;j=1,2,3};
　　E(G)={vijvi(j+1)

9、|i=1,2,3;j=1,2}∪{vk3vk1|k=1,2,3}.
　　顯然△(G)=4.
　　定理2.2.2對(duì)于上述圖G,有xp2(G)=3.
　　論文第三章主要研究了部分特殊圖的P2-染色及Pl—染色.
　　定理3.1對(duì)于n階完全圖G,有xp2(G)=[n/3].
　　定義3.1對(duì)于任意圖G=(V1,E1)和H=(V2,E2),笛卡爾乘積圖定義如下:
　　V(G□H)=V1×V2={(vi,vj)

10、|(?)ui∈V1,vj∈V2};
　　E(G□H)={(u1,v1),(u2,v2)|v1=v2且(u1,u2)∈E1或u1=u2且(u1,u2)∈E2}.
　　定理3.2對(duì)于任意n階圖G及有t個(gè)頂點(diǎn)的路Pt-1,若xpl(G)=k且k>2.l≥0,則xpl(Pt-1□G)=k.
　　定理3.3對(duì)于任意n階圖G及有t個(gè)頂點(diǎn)的圈Ct,若xpl(G)=k且k≥3,l≥0,則xpl(Ct□G)=k.
　　當(dāng)χρl(G