论文部分内容阅读
本文用[x]表示不大于实数z的最大整数.用[s]表示集合S中元素的个数.
除非特别指出,本文所讨论的图均为简单,有限,无向图.用V(G)和E(G)分别表示图G的顶点集和边集.对于任意顶点v∈V(G),用dG(u)表示顶点v在图G中的度.N(v)表示点v,的邻域,用δ(G)表示图G中顶点的最小度.G[v]表示图G由顶点子集V导出的子图.K<,v>表示n个顶点的完全图.a(G)表示图G的独立数,xf(G)表示图G的分数色数.本文所用术语与符号基本与文献[1]中一致.
随着图的染色问题在现实中被广泛应用,它逐渐成为众多学者研究的重要领域之一. E.Scheinerman和D.Ullman在[2]中提出了分数染色的概念,它是图染色的分数推广.作者并指出:确定任意一个图的分数色数是NP-完全问题.
在本文中,关于图的分数染色,我们主要得到如下定理:
定义1 G足一个图,若对G的每个真子图H有xf(H)(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)-分数染色临界图,则δ(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必不是分数染色临界图.
定理2.1.9 若u,v是分数染色临界图G的两个顶点,则N(u)不是N(v)的子集.
定理2.1.10 若G为n-临界图,且Xf(G)=X(G),则 ∈V(G) E(G)有Xf(G-t)=Xf(G)-1.
定理2.1.11 若G为n-临界图,当x(G)-λf(G)<1时,则G为分数染色临界图.
定理2.1.12图G为分数染色临界图,且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>将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<,1>),X<,F>(G<,2>)}.
注:上下界不能改进.(2)将Yi与Xi+1合成一个点,i:0,1,2,…,n-1,(下标取模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.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.ei=X<,i>Y<,i>∈E(G<,i>),令C<,2k>=(C<,2k>,…,c2k-1)为长为2k的圈.构造新图:(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合成一个点,下标模2k.
令此图S<,3>(G<,0>.e<,0>.G<,1>.e<,1>.G<,2>.e<,2>.….G<,1k-1>.e<,1k-1>).简记为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,若分数色数最大者非分数染色临界图,则Xf(S<,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.构造新图如下:(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>与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}注;其上下界不能改进.
推论2.2.13 对上述S<,4>图中G<,i>:i=1,2,…,7,若分数色数最大者非分数染色临界图,则xf(S<,4>)=max{λf(G<,i>):i=1,2,…,7).
定义7距离联图GV<,D>G,G为G的复制, 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)∪{(i,j)d(i"j")=k,k∈D,i"为i∈V(G)的对应点}.
定理2.3.2 GV<,D>G.D={0.1}是距离联图,则Xf(GV<,D>G)=2Xf(G).
定理2.3.3 若G为分数染色临界图,则距离联图GV<,D>G,D={0,1}为分数染色临界图.定理2.3.6 距离联图C<,n>V<,D>C<,n>＇,D={k,k+1},k≤m-1.则xf(C<,n>V,,D>C<,n>＇)≤2xf(C<,n>).
注:a(G)=m,等号成立.
定理2.3.7 距离联图C<,n>V<,D>C<,n>＇,D={k,k+2}…,k+i},i为偶数,且k+i≤m则
定理2.4.1 C为任意图,xf(G)=a/b且G有一个a:b染色,则图μm(G).整数m≥0.xf(μm(G)≤其中B=B+b(n-b)+…+b(a-b)+(a-b).
定理2.4.2 图,μm(K<,n>),整数m≥1.n≥3.为分数染色临界图定理2.4.3 GVG是上述图,则xf(GVG):xf(V)+1.