试析染几类全染色理由中专生

论文导读：的一个-T-全染色.记χrT,sT,tT(G,T)是使得G有一个-T全染色的最小的k.在本论文中,我们主要得到了如下结论：定理2.1.13如果图G是二部图,则r≥s(χ′(G)-1)+2时,χr,s,1(G)=χr,0,0(G);如果图G是非二部图,则r≥(sχ′(G))/(χ(G)-s12下一页
摘要：图论是数学的一个重要分支,它虽然是一门非常年轻的学科,但是进展成熟很快.图的染色不足是图论中探讨的主要不足之一,有着很好的论述探讨价值和实际作用.频率分配不足是指对每一个无线电发射台分配一个频率,使得相互干扰的无线电发射台所分配的频率间隔在允许的范围内.但是在一些频率分配不足中,相邻的接收站要求有比较大的频率间隔,稍近的的一些接收站也让它们分配不同的频道,即如果两个接收站是相邻的,那么分配给它们的频率至少差2.如果两个接收站距离为2,那么分配给它们的频率不同.对于这种情况,1992年,Griggs和Yeh提出了L(2,1)-标号不足,它是上面陈述的频率分配不足的一种图论模型.2000年,G.J,Chang等人把它推广到图的L(p,1)-标号.本论文只考虑简单连通图G.定义1[10]图G的一个L(p,1)-标号是一个以G的顶点集V(G)到整数集的映射L:V(G)→{0,1,…,k}(1)对任意的u,v∈V(G),若d(u,v)=1,则|L(u)-L(v)|≥p;(2)对任意的u,v∈V(G),若d(u,v)=2,则|L(u)-L(v)|≥1.Whittleseyet等人在文献中[24]中探讨了图G的第一剖分图的L(p,1)-标号.图G的第一剖分图的s1(G)就是图G通过每一条边上加一个点得到的.图G的第一剖分图的s1(G)的L(p,1)-标号是对应于图G的一个特别的全染色.这种全染色是由Het和yu[7]提出的(p,1)-全标号.定义2[7]图G的(p,1)-全标号是满足下面三个条件的映射c:V(G)∪E(G)→{0,1,…,k}(1)对任意的u,v∈V(G)若uv∈E(G)则c(u)-c(v)|≥1;(2)对任意的u,v,w∈V(G)若uv,uw∈E(G)则|c(uv)-c(uw)|≥1;(3)对任意的u,v∈V(G)若uv∈E(G)则|c(u)-c(uv)|≥p.(p,1)-全标号的跨度是指标号中的最大标号与最小标号的差.图G的所有(p,1)-全标号中最小的跨度,称为图G的(p,1)-全标号数,记为λpT(G).Fredeic Het和Min-LinYu在文献[7]中给出了λpT(G)的平凡上下界,提出了著名的(p,1)-全标号猜想：λpT(G)≤min{Δ(G)+2p-1,2Δ(G)+p-1}并且证明了对任意的图G,有λpT(G)≤2Δ(G)+p-1.图G的[r,s,t]-染色是对传统全染色的推广,其定义如下：定义3[1]图G的[r,s,t]-染色是一个映射c:V(G)∪E(G)→{0,1,…,k-1},使得对于给定的非负整数r,s,t满足：(1)任意两个相邻的点vi,vj,有|c(vi)-c(vj)|≥r;(2)任意两条相邻的边ei,ej,有|c(ei)-c(ej)|≥s;(3)任意一对关联的点和边vi,ej,有|c(vi)-c(ej)|≥t.G的[r,s,t]-色数χr,s,t(G)是使得G有一个[r,s,t]-染色的最小的k.显然r=1,s=t=0时就是正常的点染色, r=t=0,s=1时就是正常的边染色,r=s=t=1时就是正常的全染色,r=s=l,t=p时就是(p,1)-全标号.Hajo Broera在2007年对正常的点染色在支撑树上限制,提出了一种新的染色-Backbone coloring这里我们将沿用这种思想把[r,s,t]-染色的条件限制在支撑树上.对任意连通图G,都有支撑树,所以我们引入以下定义：定义4给定一个简单连通图G.k为一个正整数.c是G的一个正常全染色：V(G)∪E(G)→{0,1,…,k-1}.设T是G的一棵支撑树,r,s,t均是非负整数.若：(1)对任意的u,v∈V(G),dT(u,v)=1则|c(u)-c(v)|≥r;(2)对任意的uv,uw∈E(T),|c(uv)-c(uw)|≥s;(3)对任意的u∈V(G),uv∈E(T),|c(u)-c(uv)|≥t则称c为G的一个[r,s,t]-T-全染色.记χrT,sT,tT(G,T)是使得G有一个[r,s,t]-T全染色的最小的k.在本论文中,我们主要得到了如下结论：定理2.1.13如果图G是二部图,则r≥s(χ′(G)-1)+2时,χr,s,1(G)=χr,0,0(G);如果图G是非二部图,则r≥(sχ′(G))/(χ(G)-s论文导读：')={v1,v2,…,vn,v'1,v'2,…,v'n),E(G')={vivj,v'ivj,viv'j,v'iv'j|vivj∈E(G)},则G'称为图G的点分裂图.定理3.2.2若图G'为连通图G的分裂图,△(G)=△,则G有着一棵支撑树T',使得χrT′,1T′,1T′(G′,T′)≤4△+2r.关键词：（p论文1）-全标号论文（p论文1）-全标号数论文-染色论文-染色数论文支撑树
)+1且r不是s的倍数时,χr,s,1(G)=χr,0,0(G).对于二部图,定理中给出的下界是紧的.定理2.1.14如果Δ(G)≥2,χ′(G)=Δ(G)且s≥2r,r≥2t时,χr,s,t(G)=χ0,s,0(G).定理2.1.15设G是一个图,χ′(G)=Δ(G)+1若s-t≥r≥t则χr,s,t(G)=χ0,s,0(G).定理2.2.16任意图G,Δ(G)≥6,则λ3T(G)≤2Δ(G)+1.定理2.2.17对任意的简单图G,其最大度为Δ(G),如果Δ(G)是偶数且至少是6,则λ2T(G)≤2Δ(G)-1.定理3.1.2对任意简单连通图G,设其最大度为Δ,T是G的任意一棵支撑树,则χrT,1T,1T(G,T)≤2Δ+2r.定理3.1.3对任意简单连通图G,设其最大度为△且s≥[Δ/(Δ-1)],T是G的任意一棵支撑树,则χrT,sT,1T(G,T)≤(2s+1)Δ-2s+2r+2.定理3.2.1设G是一个简单连通图,其最大度为△,若G有着一棵支撑树T0且满足：T0的度为1的点在G中都不是最大度点,则χrT0,1T0,1T0(G,T0)≤2Δ+2r-1.若简单图G=(V(G),E(G)),V(G)={v1,v2,…,vn},定义G'的顶点集和边集如下：V(G')={v1,v2,…,vn,v'1,v'2,…,v'n),E(G')={vivj,v'ivj,viv'j,v'iv'j|vivj∈E(G)},则G'称为图G的点分裂图.定理3.2.2若图G'为连通图G的分裂图,△(G)=△,则G有着一棵支撑树T',使得χrT′,1T′,1T′(G′,T′)≤4△+2r.关键词：（p论文1）-全标号论文（p论文1）-全标号数论文[r论文s论文t]-染色论文[r论文s论文t]-染色数论文支撑树论文[r论文s论文t]-T-全染色论文
本论文由www.7ctime.com,需要论文可以联系人员哦。中文摘要5-9
ABSTRACT9-13
第一章 引言13-19
§

1.1 基本概念与符号14-15

§

1.2 图染色的历史与进展15-19

第二章 图的[r,s,t]-染色19-30
§

2.1 图的某些[r,s,t]-染色的色数19-22

§

2.2 图的(p,1)-全标号的两个结果22-29

进一步探讨的不足29-30
第三章 图的[r,s,t]-T-全染色30-36
§

3.1 图的[r,s,t]-T-全染色的两个上界30-33

§

3.2 几类特殊图的[r,s,t]-T-全染色33-35

进一步探讨的不足35-36
参考文献36-40
在学期间发表的学术论文40-41
致谢41