與頻道分配有關(guān)的兩類圖染色問題.pdf

1、圖的染色問題是圖論的主要研究領(lǐng)域之一，是圖論研究中很活躍的一個課題，它在組合分析和實際生活中有廣泛的應(yīng)用。隨著科技的發(fā)展，經(jīng)典的各類染色已經(jīng)不能滿足要求，于是產(chǎn)生了許多新的染色。 設(shè)G是一個無環(huán)邊的圖．G的頂點正常k染色是指k種顏色1，2，…，k對于G的各頂點的一種分配，使得任意相鄰的頂點被染上不同的顏色．令X(G)=min，{k|G是k色可染的)，稱X(G)為G的點色數(shù)，有時簡稱為色數(shù)，圖G的邊正常k染色是指k種顏色1，2，…

2、，k對E(G)中元素的一種分配，使得相鄰兩條邊所染顏色不同．令X'(G)=min，{k|G是邊k色可染的}稱為G的邊色數(shù)。 Gringgs和Yeh引進(jìn)了L(2，1)—標(biāo)號[1]，它的自然推廣是L(p，1)—標(biāo)號[3]．圖G的一個L(p，1)—標(biāo)號是從V(G)到一個整數(shù)集合的映射L，必須滿足：對于任意的頂點u，v (1)若dG(u，v)=1，貝| L(u)— L(v)|≥p； (2)若dG(u，v)=2，則|L(

3、u)— L(v)|≥1。 圖G的L(p，1)—標(biāo)號在頻率分配中有很強的應(yīng)用背景．Whittleseyet等人在文章[4]中研究了圖G的第一剖分圖的L(2，1)—標(biāo)號．圖G的第一剖分圖s1(G)是圖G通過在每條邊上加一個點得到的．圖s1(G)的L(p，1)—標(biāo)號對應(yīng)于從V(G)∪ E(G)到一個整數(shù)集合的映射，這個映射必須滿足： (1)圖G的任意兩個相鄰的頂點得到不同的整數(shù)； (2)圖G的任意兩個相鄰的邊得到不同的

4、整數(shù)； (3)圖G的任意一個頂點和它所關(guān)聯(lián)的邊得到的整數(shù)必須至少相差p．我們把這種映射稱為圖G的(p，1)—全標(biāo)號。 一個(p，1)—全標(biāo)號的跨度[2]是指最大標(biāo)號數(shù)與最小標(biāo)號數(shù)的差，圖G的所有(p，1)—全標(biāo)號中最小的跨度，稱為圖G的(p，1)—全標(biāo)號數(shù)[2]，記為λTp(G)．目前對圖的(p，1)—全標(biāo)號的研究還比較初步.Fredeic Havet和Min—Li Yu在文章[2]中給出了λTp(G)的平凡的上下界，提

5、出了(p，1)—全標(biāo)號猜想：λ(G)≤△(G)+2p-1。 文章[5]中的泛寬度染色是新提出的另一種在頻率分配問題上有很強應(yīng)用的一種染色．泛寬度染色是對點染色的推廣，是對圖頂點的一種剖分，要求把所有的頂點剖分成寬度兩兩不同的i—寬度箱Xi，即同一寬度箱Xi中任兩點的距離大于i，Xi中的頂點用同一種顏色來染．不同的寬度箱所染的顏色必須兩兩不同．圖G的泛寬度色數(shù)Xp(G)=min，{k|G是k—泛寬度可染的}。 在本文第一章

6、中，我們主要介紹了文章所涉及的一些概念、術(shù)語和符號和圖染色問題的發(fā)展情況，在第二章中，我們研究了圖的(p，1)—全標(biāo)號，其中包括外平面圖，二部圖，正則圖，Halin，圖以及定義的一種新圖．第三章中研究了圖的泛寬度染色，給出了二部圖和Mycielskian—圖的泛寬度色數(shù)的最好可能上界，給出了幾類特殊圖的泛寬度色數(shù)．文中主要得到以下結(jié)論： 定理2.1.4若圖G是一個2—連通外平面圖，且不含三角形，△(G)=3，當(dāng)p≥3時，有λTp

7、(G)=p+3。 定理2.2.2若圖G是一個二部圖，非正則，△(G)—3，且圖G中包含一個相鄰于兩個最大度點的最大度點，則λT2(G)=5。 定理2.2.4若圖G是一個二部圖，非正則，△(G)=4，且圖G的最大度生成子圖G△中包含K1，3，那么λT2(G)=6。 定理2.3.1若p＞X(G)+X'(G)—2，并且圖G是邊色數(shù)X'(G)=△(G)的△—正則圖，則λTp(G)=X(G)+X'(G)+p—2。

8、定理2.3.2若G是一個3—正則圖并且含有1—因子，則有λTp(G)≤p+5.定理2.3.3圖G是3—正則圖，且X(G)=3，p＞3，則λT2(G)≥p+4。 定義2.4.1[38]若對于孓連通平面圖G，去掉G中某個面fo的邊界上的所有邊后，G變成一棵樹，并且屬于V( fo)的所有頂點的度數(shù)是3，那么把G稱作Halin圖，屬于V(fo)的頂點稱為G的外部點，其余的頂點稱為G的內(nèi)部點．定理2.4.3圖G是一個3—正則Halin，圖

9、，則5≤λT2(G)≤6.定理2.4.5圖G是一個Halin，圖，且△(G)=4，則λT2(G)≤6。 定義2.5.1 G表示任意一個連通圖，其中V(G)={v1，v2，…，vn}．G'表示圖G的復(fù)制圖，其中V(G')={v'1，v'2，…，v'n)．新圖D(G)是由圖G，G'經(jīng)過下述構(gòu)造得到的圖：把圖G中的每個頂點和圖G'中所對應(yīng)的復(fù)制點連起來，其中V(D(G))=V(G)∪V(G')，E(D(G))=E(G)∪E(G') U

10、{v1v'1，V2V'2，…，Vnv'n}，不妨稱為雙圖D(G)。 定理2.5.1 Cn表示一個圈，則λT2(D(Cn))=5。 定理2.5.2對于任意的連通圖G，滿足λT2(G)=△+4，那么雙圖D(G)的全標(biāo)號數(shù)λT2(D(G))≤λT2(G)+1。 定理3.1.1對任意的自然數(shù)m，n，Gm，n是二部圖，我們有Xp(Gm，n)≤min{m，n}+1，并且這個上界是最好可能的。 簡單圖的Mycielsk