论文部分内容阅读
图的染色问题是图论研究中一个活跃的领域，因此各类染色问题被相继提出并加以发展应用，赖宏建等人在2006年提出了条件染色．图的标号问题就是图的染色问题的推广，其理论研究背景是频道分配问题．Griggs和Yeh在1992年提出了L(2，1)—标号问题，作为标号问题的另一种推广，孙磊老师于2008年提出了邻域限制标号问题．
条件染色是传统的点染色在理论上的自然地推广，是在文献[2]中首次提出的．对于整数k＞0和r＞0，图G的一个正常(k，r)—染色[2]是一个满足下面两个条件的映射c：V(G)→{1，2…k}，
(1)若uv∈E(G)，则c(u)≠c(v)；
(2)对任意的v∈V(G)，|c(NG(v))|≥min{|NG(v)|，r}．
对于固定的r，使G有一个正常的(k，r)—染色的最小的k是图G的第r个条件色数，记为Xr(G)．由条件色数的定义很显然的得到X1(G)=X(G)．
作为频率设置问题的一个变形，Griggs和Yeh在1992年提出了L(2，1)—标号问题．图G的一个L(2，1)—标号[1]是一个满足下面两个条件的映射c：V(G)→{0，1，2…k}，
(1)对任意的u，v∈V(G)，若d(u，v)=1，则|c(u)— c(v)|≥2；
(2)对任意的u，v∈V(G)，若d(u，v)=2，则|c(u)— c(v)|≥1.当所有的标号都小于等于k时，称图G有一个k— L(2，1)—标号．则使得图G有一个k— L(2，1)—标号的最小的正整数k称为图G的L(2，1)—标号数，记为λ(G)．令c是图G的一个的λ(G)— L(2，1)—标号．令c-1(i)={v∈V(G)|c(v)=i}且令|c-1(i)|表示c-1(i)的基数．若对于一个整数h(0＜h＜l)满足|c-1(h)|=0，则称h为c的—个洞．图G的洞数，记为p(G)[δ]，是图G的所有λ(G)— L(2，1)—标号中最少的洞的个数．
对于一个整数k＞0，图G的一个k—L1，2—标号是一个满足下面两个条件的映射c：V(G)→{0，1，2…k}，
(1)任意的u，v∈V(G)，若d(u，v)=1，则|c(u)— c(v)|≥1；
(2)任意的u，v∈V(G)，若存在w∈V(G)，使得u，v∈NG(w)，则|c(u)—c(v)|≥2.则使得图G有一个k—Li，2—标号的最小的正整数七称为图G的邻域限制标号数，记为L1，2(G)．令c是图G的—个的k—L1，2—标号．令c-1(i)={v∈V(G)|c(v)=i}且令|c-1(i)|表示c-1(i)的基数．若对于一个整数h(0＜h＜k)满足|c-1(h)|=0，则称h为c的一个洞．
本文中△(G)表示图G的最大度，δ(G)表示图G的最小度，d(u，v)表示u，v两点在图G中的距离，NG(v)表示v在图G中的邻域，在本文的第二章我们主要得到了以下结论．
引理2.1.1图G是任意简单图，则L1，2(G)≥2(△(G)-1)．
引理2.1.2图G是任意简单图，且L1，2(G)=2(△(G)-1)．则任意的最大度点v，c(v)≡1(mod2)，且任意的u∈NG(v)，c(u)=2i(i=0，1，2…△(G)-1)．
定理2.1.3若图G中有两个最大度点相邻，则L1，2(G)≥2△(G)-1.
定理2.1.4若正则图G中有奇圈且△≥4，则L1，2(G)≥2△(G)．
定理2.1.5图G是圈，则当|V(G)|≡0(mod4)时，L1，2(G)=3；否则，L1，2(G)=4.
定理2.1.6设图G是k—退化图，△≥4且无三角，则2(△-1)≤L1，2(G)≤△(6k—3)+k—3k2.
定理2.2.1设图G是树，△(G)≥3，且图G中有两个最大度点相邻，则L1，2(G)=2△(G)-1.
定理2.2.3设图G是树，△(G)≥3，若图G中无最大度点相邻且任意两个最大度点的距离为偶数，则L1，2(G)=2(△(G)-1)．
定理2.2.4设图G是树，△(G)≥4，若存在一条包含所有最大度点的路．则当图G中无两个最大度点不相邻且存在两个最大度点的距离为奇数时，L1，2(G)=2(△(G)-1)．
定理2.2.5设图G是树，△(G)≥3，若图G中只有一个最大度点，则L1，2(G)=2(△(G)-1)．
我们证明了当c是G的—个最小的邻域限制标号，且h是c的一个洞，图G具有的下述性质．
性质2.3.1图G是任意简单图，若c是G的一个最小的邻域限制标号，且h是c的一个洞，则h-1，h+1都不是c的洞，
性质2.3.2令c是G的一个最小的邻域限制标号，h是c的一个洞．若|c-1(h-1)|≥2或|c-1(h+1)|≥2且c(u)=h-1，c(v)=h+1，则肯定存在一点x满足d(u，x)≤2且c(x)=h+1或一点y满足d(v，y)≤2且c(y)=h-1.
性质2.3.3图G是任意简单图且无三角，令c是图G的一个最小的邻域限制标号，且h是c的一个洞．若对任意的标号i，满足|c-1(i)|≥2，则若c(v)：h-1或h+1，则肯定存在两点v1，v2满足d(v，v1)=1，d(v，V2)=2，c(v1)=c(v2)=h+1或h-1且V2()NG(v1)．
性质2.3.4图G是任意简单图且无三角，令c是G的一个最小的邻域限制标号，且h是c的一个洞．若存在路uvov，满足c(u)=h-1，c(v)=h+1且任意的x满足d(u，x)=2，但c(x)≠h+1且任意的y满足d(v，y)=2，但c(y)≠h-1.则此时|c-1(c(vo))|=1.
性质2.3.5图G是任意简单图且无三角，令c是G的一个最小的邻域限制标号，h是c的一个洞，且|c-1(h-1)|=1，| c-1(h+1)|≥2.若令c(u)=h-1，则对任意的vi满足c(vi)=h+1，存在路uwivi．若任意的ui满足d(u，vi)≠1，则|c-1(c(wi》|=1.或有且仅有一个vi满足d(u，vi)≠1.
G是一个简单图，V(G)=．[v1，v2，…，vn}，G[I2]的点集和边集如下定义：V(G[I2])={v1，v2，…，vn，v1，v2，…，Vn}，E(G[I2])=E(G)∪{vivj，vivj|vivj∈E(G)}，则G[I2]称为G的点分裂图[37]．令G=(V(G)，E(G))，V(G)={v1，v2，v3，…vn}，M—构造图M(G)[38]的点集和边集是如下定义的，V(M(G))={v1，…vn，u1，…un，v}，E(M(G))={uiv|i=1，2…n}∪{uivj|vivj∈E(G)}．M—构造图在研究图染色问题的临界性上有重要应用．在本文的第三章我们讨论了图G与其分裂图G[I2]的条件色数的关系及图G与其M—构造图M(G)的条件色数的关系，给出了几类特殊图的条件色数．
定理3.1.1图G与其分裂图G[I2]的条件色数的关系如下，
定理3.2，1若整数r满足0＜r≤2△(G)，则任意的图G的M—构造图M(G)满足Xr(M(G))≥r+2.定理3.2.2图G与M—构造图M(G)的条件色数的关系如下：
对任意的正整数k和m，G(k，m)表示一些图的集合．若G∈G(k，m)当且仅当V(G)=V0∪V1∪…Vm，|V0|=|V1|=…|Vm|=h且对任意的0≤i≤m，G(Vi)的导出子图是一个空图；对任意的0≤i＜j≤m，G[Vi∪Vj]的导出子图是一个完美匹配．在本文的第四章我们主要研究G(k，m)这类图的L(2，1)—标号问题并得到了以下结论．
定理4.1k≥3，n≥2，若图G∈G(k，n+1)且包含一个子图H∈G(k，n)使得λ(H)=2n且p(H)=n，则λ(G)=2(n+1)．
定理4.2 k≥3，若G∈G(k，2)，则λ(G)=4且p(G)=0或2.
定理4.3若G∈G(3，3)，则λ(G)=6.
定理4.4若G∈G(4，3)，则λ(G)=6.