有鄰域限制的圖染色問(wèn)題及圖的L(2，1)-標(biāo)號(hào).pdf

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

2、k，r)—染色[2]是一個(gè)滿(mǎn)足下面兩個(gè)條件的映射c：V(G)→{1，2…k}， (1)若uv∈E(G)，則c(u)≠c(v)； (2)對(duì)任意的v∈V(G)，|c(NG(v))|≥min{|NG(v)|，r}． 對(duì)于固定的r，使G有一個(gè)正常的(k，r)—染色的最小的k是圖G的第r個(gè)條件色數(shù)，記為Xr(G)．由條件色數(shù)的定義很顯然的得到X1(G)=X(G)． 作為頻率設(shè)置問(wèn)題的一個(gè)變形，Griggs和Yeh在

3、1992年提出了L(2，1)—標(biāo)號(hào)問(wèn)題．圖G的一個(gè)L(2，1)—標(biāo)號(hào)[1]是一個(gè)滿(mǎn)足下面兩個(gè)條件的映射c：V(G)→{0，1，2…k}， (1)對(duì)任意的u，v∈V(G)，若d(u，v)=1，則|c(u)— c(v)|≥2； (2)對(duì)任意的u，v∈V(G)，若d(u，v)=2，則|c(u)— c(v)|≥1.當(dāng)所有的標(biāo)號(hào)都小于等于k時(shí)，稱(chēng)圖G有一個(gè)k— L(2，1)—標(biāo)號(hào)．則使得圖G有一個(gè)k— L(2，1)—標(biāo)號(hào)的最小的正

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

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有一個(gè)k—Li，2—標(biāo)號(hào)的最小的正整數(shù)七稱(chēng)為圖G的鄰域限制標(biāo)號(hào)數(shù)，記為L(zhǎng)1，2(G)．令c是圖G的—個(gè)的k—L1，2—標(biāo)號(hào)．令c-1(i)={v∈V(G)|c(v)=i}且令|c-1(

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

7、1)．則任意的最大度點(diǎn)v，c(v)≡1(mod2)，且任意的u∈NG(v)，c(u)=2i(i=0，1，2…△(G)-1)． 定理2.1.3若圖G中有兩個(gè)最大度點(diǎn)相鄰，則L1，2(G)≥2△(G)-1. 定理2.1.4若正則圖G中有奇圈且△≥4，則L1，2(G)≥2△(G)． 定理2.1.5圖G是圈，則當(dāng)|V(G)|≡0(mod4)時(shí)，L1，2(G)=3；否則，L1，2(G)=4. 定理2.1.6設(shè)圖G是

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

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

10、c是G的一個(gè)最小的鄰域限制標(biāo)號(hào)，h是c的一個(gè)洞．若|c-1(h-1)|≥2或|c-1(h+1)|≥2且c(u)=h-1，c(v)=h+1，則肯定存在一點(diǎn)x滿(mǎn)足d(u，x)≤2且c(x)=h+1或一點(diǎn)y滿(mǎn)足d(v，y)≤2且c(y)=h-1. 性質(zhì)2.3.3圖G是任意簡(jiǎn)單圖且無(wú)三角，令c是圖G的一個(gè)最小的鄰域限制標(biāo)號(hào)，且h是c的一個(gè)洞．若對(duì)任意的標(biāo)號(hào)i，滿(mǎn)足|c-1(i)|≥2，則若c(v)：h-1或h+1，則肯定存在兩點(diǎn)v1，v

11、2滿(mǎn)足d(v，v1)=1，d(v，V2)=2，c(v1)=c(v2)=h+1或h-1且V2()NG(v1)． 性質(zhì)2.3.4圖G是任意簡(jiǎn)單圖且無(wú)三角，令c是G的一個(gè)最小的鄰域限制標(biāo)號(hào)，且h是c的一個(gè)洞．若存在路uvov，滿(mǎn)足c(u)=h-1，c(v)=h+1且任意的x滿(mǎn)足d(u，x)=2，但c(x)≠h+1且任意的y滿(mǎn)足d(v，y)=2，但c(y)≠h-1.則此時(shí)|c-1(c(vo))|=1. 性質(zhì)2.3.5圖G是任意簡(jiǎn)

12、單圖且無(wú)三角，令c是G的一個(gè)最小的鄰域限制標(biāo)號(hào)，h是c的一個(gè)洞，且|c-1(h-1)|=1，| c-1(h+1)|≥2.若令c(u)=h-1，則對(duì)任意的vi滿(mǎn)足c(vi)=h+1，存在路uwivi．若任意的ui滿(mǎn)足d(u，vi)≠1，則|c-1(c(wi》|=1.或有且僅有一個(gè)vi滿(mǎn)足d(u，vi)≠1. G是一個(gè)簡(jiǎn)單圖，V(G)=．[v1，v2，…，vn}，G[I2]的點(diǎn)集和邊集如下定義：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]稱(chēng)為G的點(diǎn)分裂圖[37]．令G=(V(G)，E(G))，V(G)={v1，v2，v3，…vn}，M—構(gòu)造圖M(G)[38]的點(diǎn)集和邊集是如下定義的，V(M(G))={v1，…vn，u1，…un，v}，E(M(G))={uiv|i=1，2…n}∪{uivj|vivj∈E(G)}．M—構(gòu)造圖在研究圖染色問(wèn)題的臨界性上

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

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