有鄰域限制的圖染色問題及圖的L(2，1)-標號.pdf

1、圖的染色問題是圖論研究中一個活躍的領(lǐng)域，因此各類染色問題被相繼提出并加以發(fā)展應(yīng)用，賴宏建等人在2006年提出了條件染色．圖的標號問題就是圖的染色問題的推廣，其理論研究背景是頻道分配問題．Griggs和Yeh在1992年提出了L(2，1)—標號問題，作為標號問題的另一種推廣，孫磊老師于2008年提出了鄰域限制標號問題． 條件染色是傳統(tǒng)的點染色在理論上的自然地推廣，是在文獻[2]中首次提出的．對于整數(shù)k＞0和r＞0，圖G的一個正常(

2、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個條件色數(shù)，記為Xr(G)．由條件色數(shù)的定義很顯然的得到X1(G)=X(G)． 作為頻率設(shè)置問題的一個變形，Griggs和Yeh在

3、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)—標號的最小的正

4、整數(shù)k稱為圖G的L(2，1)—標號數(shù)，記為λ(G)．令c是圖G的一個的λ(G)— L(2，1)—標號．令c-1(i)={v∈V(G)|c(v)=i}且令|c-1(i)|表示c-1(i)的基數(shù)．若對于一個整數(shù)h(0＜h＜l)滿足|c-1(h)|=0，則稱h為c的—個洞．圖G的洞數(shù)，記為p(G)[δ]，是圖G的所有λ(G)— L(2，1)—標號中最少的洞的個數(shù)． 對于一個整數(shù)k＞0，圖G的一個k—L1，2—標號是一個滿足下面兩個條件

5、的映射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—標號的最小的正整數(shù)七稱為圖G的鄰域限制標號數(shù)，記為L1，2(G)．令c是圖G的—個的k—L1，2—標號．令c-1(i)={v∈V(G)|c(v)=i}且令|c-1(

6、i)|表示c-1(i)的基數(shù)．若對于一個整數(shù)h(0＜h＜k)滿足|c-1(h)|=0，則稱h為c的一個洞． 本文中△(G)表示圖G的最大度，δ(G)表示圖G的最小度，d(u，v)表示u，v兩點在圖G中的距離，NG(v)表示v在圖G中的鄰域，在本文的第二章我們主要得到了以下結(jié)論． 引理2.1.1圖G是任意簡單圖，則L1，2(G)≥2(△(G)-1)． 引理2.1.2圖G是任意簡單圖，且L1，2(G)=2(△(G)-

7、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設(shè)圖G是

8、k—退化圖，△≥4且無三角，則2(△-1)≤L1，2(G)≤△(6k—3)+k—3k2. 定理2.2.1設(shè)圖G是樹，△(G)≥3，且圖G中有兩個最大度點相鄰，則L1，2(G)=2△(G)-1. 定理2.2.3設(shè)圖G是樹，△(G)≥3，若圖G中無最大度點相鄰且任意兩個最大度點的距離為偶數(shù)，則L1，2(G)=2(△(G)-1)． 定理2.2.4設(shè)圖G是樹，△(G)≥4，若存在一條包含所有最大度點的路．則當圖G中無兩個

9、最大度點不相鄰且存在兩個最大度點的距離為奇數(shù)時，L1，2(G)=2(△(G)-1)． 定理2.2.5設(shè)圖G是樹，△(G)≥3，若圖G中只有一個最大度點，則L1，2(G)=2(△(G)-1)． 我們證明了當c是G的—個最小的鄰域限制標號，且h是c的一個洞，圖G具有的下述性質(zhì)． 性質(zhì)2.3.1圖G是任意簡單圖，若c是G的一個最小的鄰域限制標號，且h是c的一個洞，則h-1，h+1都不是c的洞， 性質(zhì)2.3.2令

10、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. 性質(zhì)2.3.3圖G是任意簡單圖且無三角，令c是圖G的一個最小的鄰域限制標號，且h是c的一個洞．若對任意的標號i，滿足|c-1(i)|≥2，則若c(v)：h-1或h+1，則肯定存在兩點v1，v

11、2滿足d(v，v1)=1，d(v，V2)=2，c(v1)=c(v2)=h+1或h-1且V2()NG(v1)． 性質(zhì)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. 性質(zhì)2.3.5圖G是任意簡

12、單圖且無三角，令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，…，

13、vn，v'1，v'2，…，V'n}，E(G[I2])=E(G)∪{v'iv'j，v'ivj|vivj∈E(G)}，則G[I2]稱為G的點分裂圖[37]．令G=(V(G)，E(G))，V(G)={v1，v2，v3，…vn}，M—構(gòu)造圖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òu)造圖在研究圖染色問題的臨界性上

14、有重要應(yīng)用．在本文的第三章我們討論了圖G與其分裂圖G[I2]的條件色數(shù)的關(guān)系及圖G與其M—構(gòu)造圖M(G)的條件色數(shù)的關(guān)系，給出了幾類特殊圖的條件色數(shù)． 定理3.1.1圖G與其分裂圖G[I2]的條件色數(shù)的關(guān)系如下， 定理3.2，1若整數(shù)r滿足0＜r≤2△(G)，則任意的圖G的M—構(gòu)造圖M(G)滿足Xr(M(G))≥r+2.定理3.2.2圖G與M—構(gòu)造圖M(G)的條件色數(shù)的關(guān)系如下： 對任意的正整數(shù)k和m，G(k，m

15、)表示一些圖的集合．若G∈G(k，m)當且僅當V(G)=V0∪V1∪…Vm，|V0|=|V1|=…|Vm|=h且對任意的0≤i≤m，G(Vi)的導(dǎo)出子圖是一個空圖；對任意的0≤i＜j≤m，G[Vi∪Vj]的導(dǎo)出子圖是一個完美匹配．在本文的第四章我們主要研究G(k，m)這類圖的L(2，1)—標號問題并得到了以下結(jié)論． 定理4.1k≥3，n≥2，若圖G∈G(k，n+1)且包含一個子圖H∈G(k，n)使得λ(H)=2n且p(H)=n，