圖的分?jǐn)?shù)染色.pdf

1、本文用[x]表示不大于實數(shù)z的最大整數(shù).用[s]表示集合S中元素的個數(shù). 除非特別指出,本文所討論的圖均為簡單,有限,無向圖.用V(G)和E(G)分別表示圖G的頂點集和邊集.對于任意頂點v∈V(G),用dG(u)表示頂點v在圖G中的度.N(v)表示點v,的鄰域,用δ(G)表示圖G中頂點的最小度.G[v']表示圖G由頂點子集V'導(dǎo)出的子圖.K<,v>表示n個頂點的完全圖.a(G)表示圖G的獨立數(shù),xf(G)表示圖G的分?jǐn)?shù)色數(shù).本文所

2、用術(shù)語與符號基本與文獻[1]中一致. 隨著圖的染色問題在現(xiàn)實中被廣泛應(yīng)用,它逐漸成為眾多學(xué)者研究的重要領(lǐng)域之一. E.Scheinerman和D.Ullman在[2]中提出了分?jǐn)?shù)染色的概念,它是圖染色的分?jǐn)?shù)推廣.作者并指出:確定任意一個圖的分?jǐn)?shù)色數(shù)是NP-完全問題. 在本文中,關(guān)于圖的分?jǐn)?shù)染色,我們主要得到如下定理: 定義1 G足一個圖,若對G的每個真子圖H有xf(H)

3、.1 分?jǐn)?shù)染色臨界圖的頂點割不足團.推論2.1.2每個分?jǐn)?shù)染色臨界圖是2連通的. 定理2.1.3 圖G,v,∈ V(G),X N<,G>(v)是G的團. G'由G刪去所有{uz:x∈X),則Xf(G')≥Xf(G)-1. 推論2.1.4 圖G,e∈E(G),則有Xf(G-e)≥Xf(C)-1. 定理2.1.5 圖G,v∈V(G),則有Xf(G-v)≥Xf(G)-1.. 定理2.1.6,若圖G是Xf(G

4、)-分?jǐn)?shù)染色臨界圖,則δ(G)≥[Xf(G)]-2. 推論2.1.7 每個圖G至少有[Xf(G)]-1個度不少于[Xf(G)]-2的頂點. 定理2.1.8 若圖G,H滿足G≠K<,n>,H≠K<,n>n≥1,則G V H必不是分?jǐn)?shù)染色臨界圖. 定理2.1.9 若u,v是分?jǐn)?shù)染色臨界圖G的兩個頂點,則N(u)不是N(v)的子集. 定理2.1.10 若G為n-臨界圖,且Xf(G)=X(G),則 ∈V(G)

5、 E(G)有Xf(G-t)=Xf(G)-1. 定理2.1.11 若G為n-臨界圖,當(dāng)x(G)-λf(G)<1時,則G為分?jǐn)?shù)染色臨界圖. 定理2.1.12圖G為分?jǐn)?shù)染色臨界圖,且X(G)=X<,f>(G).若Xf(G)-Xf(G-t)<1. ∈V(G)∪E(G).則G不是臨界圖. 定義2<'[8]>Hajós sumG.G=(G<,1>x<,1>y<,1>+(G<,2>.x<,2>y<,2>)是由G<,1> G<,2

6、>將x<,1>.x<,x>合成個點,刪去邊x<,1>y<,1>,x<,2>y<,2>增加邊y<,1>y<,2>所得.其中x<,1>y<,1>∈E(G<,1>).x<,2>y<,2>∈E(G<,2>). 定理2.2.1 Hajós sumG=(G<,1>.x<,1>y<,1>)+(G<,2>,x<,2>y<,2>), 則 max{X<,f>(G<,1>,X<,f>(G<,2>)}-1≤X<,f>(G)≤max{X<,f>(G<

7、,1>),X<,F>(G<,2>)}. 注:上下界不能改進.(2)將Yi與Xi+1合成一個點,i:0,1,2,…,n-1,(下標(biāo)取模n),(3)連接邊x<,i>與x<,i>+2,i=0,1,2,…,n-1,(4)增加點u并連接點u與x<,i>,i=0,1,2,…,n-1,令此圖為S<,2>(G<,0>,e<,i>,G<,1>,e<,1>,G<,2>,e<,2>,…,G<,n-1>,e<,n-1>簡記為S<,2>. 定理2.2

8、.9 S<,2>為上述圖,則max{x(G<,i>):i=1,2,…,n-1}-1≤xf(S<,2>)≤max{xf(G<,i>):i=1,2 ,…,n-1)+I. 注:其下界不能改進. 定義5<'[10]>給4k個圖G<,0>,G<,1>,G<,2>,…G<,4k-1>,k≥3,i=0,1,…,4k<'i>.ei=X<,i>Y<,i>∈E(G<,i>),令C<,2k>=(C<,2k>,…,c2k-1)為長為2k的圈.構(gòu)造

9、新圖:(1)刪去e<,i>,i=0.1.2.…,4k-1.(2)將X<,0>.x<,1>….X<,2k>-1合成一個點X.對i=0.1.2.….2k-1,將yi與Ci合成一個點,(3)對i=2k,2k+1.….,lk-1.將.xi與ci-2k合成一個點, Yi與Ci-2k+3合成一個點,下標(biāo)模2k. 令此圖S<,3>(G<,0>.e<,0>.G<,1>.e<,1>.G<,2>.e<,2>.….G<,1k-1>.e<,1k-1>)

10、.簡記為S<,3>. 定理2.2.10 S<,3>為上述圖,若max{Xf(G<,i>:i=0.1,2.…,4k-1)≥7.則 max{xf(Gi):i=0.1.2.….4k-1)-1 }-1≤xf(S3)≤max{Xf(G<,i>):i=0,1,2.….4k-1}. 注:其上下界不能改進. 推論2.2.11 對上述S<,3>圖中G<,i>:i=0.1.…..4k-1,若分?jǐn)?shù)色數(shù)最大者非分?jǐn)?shù)染色臨界圖,則Xf(S<

11、,3>)=max{xf(G<,i>):i=0.1.….4K-1}. 定義6<'9>給定7個圖G<,1>.G<,2>.….G<,7>.P<,5>為5個點的路.令e<,i>=xiyi∈E(G<,i>).i=1.2.….7.構(gòu)造新圖如下:(1)刪去邊e<,i>=1.2.….7.(2)將y1.y2.y3.y4.y5.合成一個點,記為y.將xi與P<,i>合成一個點,記為x<,i>i=1.2.….5.(3)將x<,6>與x<,2>.y<,6

12、>與x<,5>..x<,7>與x<,1>.y<,7>與x<,4>分別合成一點. 記此圖為S<,4>(G<,1>.e<,1>_.G<,2>.e<,2>….G<,7>.e<,7>).簡記為S<,4>. 定理2.2.12 S<,4>為上述圖,若max{λf(Gi):i=1,2,…,7}≥6,則max{xf(G<,i>): i=1.2,….7}-1≤ x<,f>(S<,4>)≤ max{λf(Gi):i=1.2.…,7}注;其上下界

13、不能改進. 推論2.2.13 對上述S<,4>圖中G<,i>:i=1,2,…,7,若分?jǐn)?shù)色數(shù)最大者非分?jǐn)?shù)染色臨界圖,則xf(S<,4>)=max{λf(G<,i>):i=1,2,…,7). 定義7距離聯(lián)圖GV<,D>G',G'為G的復(fù)制, V{G)={1',2',…,n'),V(G')={1",2",…,n"),D=N ∪{0),V(GV<,D>G')=V(G)∪V(G'),E(GV<,D>G')=E(G)∪E(G')∪

14、{(i',j'')d(i"j")=k,k∈D,i"為i'∈V(G)的對應(yīng)點}. 定理2.3.2 GV<,D>G'.D={0.1}是距離聯(lián)圖,則Xf(GV<,D>G')=2Xf(G). 定理2.3.3 若G為分?jǐn)?shù)染色臨界圖,則距離聯(lián)圖GV<,D>G',D={0,1}為分?jǐn)?shù)染色臨界圖.定理2.3.6 距離聯(lián)圖C<,n>V<,D>C<,n>＇,D={k,k+1},k≤m-1.則xf(C<,n>V,,D>C<,n>＇)≤2xf

15、(C<,n>). 注:a(G)=m,等號成立. 定理2.3.7 距離聯(lián)圖C<,n>V<,D>C<,n>＇,D={k,k+2}…,k+i},i為偶數(shù),且k+i≤m則 定理2.4.1 C為任意圖,xf(G)=a/b且G有一個a:b染色,則圖μm(G).整數(shù)m≥0.xf(μm(G)≤其中B'=B<'m>+b<'m-1>(n-b)+…+b(a-b)<'m-1>+(a-b)<'m>. 定理2.4.2 圖,μm(K<,