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

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

2、，k對(duì)E(G)中元素的一種分配，使得相鄰兩條邊所染顏色不同．令X'(G)=min，{k|G是邊k色可染的}稱為G的邊色數(shù)。 Gringgs和Yeh引進(jìn)了L(2，1)—標(biāo)號(hào)[1]，它的自然推廣是L(p，1)—標(biāo)號(hào)[3]．圖G的一個(gè)L(p，1)—標(biāo)號(hào)是從V(G)到一個(gè)整數(shù)集合的映射L，必須滿足：對(duì)于任意的頂點(diǎn)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)號(hào)在頻率分配中有很強(qiáng)的應(yīng)用背景．Whittleseyet等人在文章[4]中研究了圖G的第一剖分圖的L(2，1)—標(biāo)號(hào)．圖G的第一剖分圖s1(G)是圖G通過在每條邊上加一個(gè)點(diǎn)得到的．圖s1(G)的L(p，1)—標(biāo)號(hào)對(duì)應(yīng)于從V(G)∪ E(G)到一個(gè)整數(shù)集合的映射，這個(gè)映射必須滿足： (1)圖G的任意兩個(gè)相鄰的頂點(diǎn)得到不同的整數(shù)； (2)圖G的任意兩個(gè)相鄰的邊得到不同的

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

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

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

7、(G)=p+3。 定理2.2.2若圖G是一個(gè)二部圖，非正則，△(G)—3，且圖G中包含一個(gè)相鄰于兩個(gè)最大度點(diǎn)的最大度點(diǎn)，則λT2(G)=5。 定理2.2.4若圖G是一個(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是一個(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]若對(duì)于孓連通平面圖G，去掉G中某個(gè)面fo的邊界上的所有邊后，G變成一棵樹，并且屬于V( fo)的所有頂點(diǎn)的度數(shù)是3，那么把G稱作Halin圖，屬于V(fo)的頂點(diǎn)稱為G的外部點(diǎn)，其余的頂點(diǎn)稱為G的內(nèi)部點(diǎn)．定理2.4.3圖G是一個(gè)3—正則Halin，圖

9、，則5≤λT2(G)≤6.定理2.4.5圖G是一個(gè)Halin，圖，且△(G)=4，則λT2(G)≤6。 定義2.5.1 G表示任意一個(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è)頂點(diǎn)和圖G'中所對(duì)應(yīng)的復(fù)制點(diǎn)連起來，其中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表示一個(gè)圈，則λT2(D(Cn))=5。 定理2.5.2對(duì)于任意的連通圖G，滿足λT2(G)=△+4，那么雙圖D(G)的全標(biāo)號(hào)數(shù)λT2(D(G))≤λT2(G)+1。 定理3.1.1對(duì)任意的自然數(shù)m，n，Gm，n是二部圖，我們有Xp(Gm，n)≤min{m，n}+1，并且這個(gè)上界是最好可能的。 簡單圖的Mycielsk