兩類特殊圖的泛寬度染色

劉秀麗

（菏澤學(xué)院數(shù)學(xué)系，山東 菏澤 274015）

兩類特殊圖的泛寬度染色

劉秀麗

（菏澤學(xué)院數(shù)學(xué)系，山東 菏澤 274015）

研究了圖染色問(wèn)題中與頻道分配有關(guān)的泛寬度染色.給出了兩類特殊圖的泛寬度色數(shù).

泛寬度染色；d-寬度箱；泛寬度色數(shù)；雙圖

0 引 言

圖論發(fā)展到現(xiàn)在已有許多分支，著色理論是其中之一，且有著極其重要的地位.它起源于150年前的四色猜想.染色問(wèn)題在組合分析和實(shí)際生活中有著廣泛的應(yīng)用，是圖論研究中一個(gè)很活躍的課題，近年來(lái)，又提出了許多新的染色問(wèn)題在頻道分配中的應(yīng)用，如Bresar等人[1]提出了一種染色-泛寬度染色.在一個(gè)給定的網(wǎng)絡(luò)中，使用相同廣播頻率的兩個(gè)站點(diǎn)的信號(hào)將會(huì)相互干擾，除非它們的位置相當(dāng)遠(yuǎn).信號(hào)傳播的距離與這些信號(hào)的功率直接相關(guān).圖的泛寬度染色是依據(jù)頂點(diǎn)之間的距離對(duì)頂點(diǎn)的一種剖分.對(duì)于不具有特定圖結(jié)構(gòu)的任意圖來(lái)說(shuō)，確定圖中任意兩個(gè)頂點(diǎn)的距離是非常困難的，而且在目前已知的結(jié)論中，也都是針對(duì)具有具體圖結(jié)構(gòu)的圖類來(lái)研究的.如在文獻(xiàn)［1］中作者給出了無(wú)限正方形和完全圖Kn的剖分圖s（Kn）的泛寬度色數(shù).Scoper[2]研究了樹的泛寬度染色，證明了無(wú)限3-正則圖樹的泛寬度色數(shù)是7.張珊珊等人[3]研究了輪、扇及完全圖Kn的推廣的hajos sum泛寬度染色，并在另一文獻(xiàn)[4]中研究了圈及其相關(guān)圖的泛寬度染色.在文獻(xiàn)［1］中作者猜想：確定任意圖的泛寬度色數(shù)問(wèn)題是NP（有非確定性多項(xiàng)式算法）完備問(wèn)題.本文研究了兩類雙圖的泛寬度色數(shù).

文中未加說(shuō)明的記號(hào)和術(shù)語(yǔ)參見(jiàn)Bondy等人文獻(xiàn)[5-6].

1 預(yù)備知識(shí)

我們用V（G）和E（G）分別表示圖G的頂點(diǎn)集和邊集.設(shè)G是一個(gè)簡(jiǎn)單圖，對(duì)于任意兩個(gè)頂點(diǎn)x，y，它們的距離d（x，y）是x-y路長(zhǎng)的最小值，特別地，如果沒(méi)有x-y路，則 d（x， y）＝ ∞.

定義1[1]設(shè)G=（V（G），E（G）），d是一個(gè)正整數(shù)，X是V（G）的一個(gè)子集，如果X中任意兩個(gè)點(diǎn)的距離都大于d，稱X是一個(gè)d-寬度箱，d叫做X的寬度，顯然，d-寬度箱也是（d-1）-寬度箱、 （d-2）-寬度箱等等.

顯然，此處我們的目的是最小化k，可以假設(shè)對(duì)每個(gè)整數(shù)i，Xi是一個(gè)i-寬度箱.

定義 3 設(shè) G 和 G′均為簡(jiǎn)單連通圖， V（G） ={v1，v2，…，vn}， V（G′） ={u1，u2，…，un}.在 G 和 G′之間加匹配 viui（i=1，2，…，n）， 得到新圖 D（G）， 我們稱 D（G）為 G 的雙圖.于是：

2 主要結(jié)果及證明

定理 1 設(shè) Pn， P′n為兩條長(zhǎng)為 n-1 的路， 其頂點(diǎn)集分別為 V（Pn） ={v1，v2，…，vn}和V（P′n） ={u1，u2，…，un}， 則當(dāng) n>5 時(shí)， 有 χρ（D（Pn）） ＝ 5.

證明 首先證明 χρ（D（Pn）） ≥ 5.

反證法，假設(shè)有一個(gè)映射 f： V（D（Pn）） → {1，2，3，4}.對(duì)于 D（Pn）上的各個(gè)頂點(diǎn)，除了v1u1，v2u2，…，vnun之外都是對(duì)稱的，不妨令f（u2）＝1.因?yàn)椋?/p>

所以可以用 1 來(lái)染 uj（j≡ 0（mod2））， 即當(dāng) j≡ 0（mod2）時(shí)， f（uj） ＝ 1； 又因?yàn)椋?/p>

所以可以用 1 來(lái)染 vi（i≡ 1（mod2））， 即當(dāng) i≡ 1（mod2）時(shí)， f（vi） ＝ 1.

對(duì)于剩余的未染色的頂點(diǎn)，不妨令f（v2）＝2.因?yàn)椋?/p>

所以可以用 2 來(lái)染 vi，uj（i≡ 2（mod6）， j≡ 5（mod6））， 即當(dāng) i≡ 2（mod6），j≡ 5（mod6）時(shí)， f（vi） ＝ 2， f（uj） ＝ 2.

類似可以用 3 來(lái)染 vi，uj（i≡ 4（mod6）， j≡ 1（mod6））， 即當(dāng) i≡ 4（mod6）， j≡1（mod6）時(shí)， f（vi） ＝ 3，f（uj） ＝ 3.

此時(shí)還剩余形如 vi（i≡ 0（mod6））和 uj（j≡ 3（mod6））的點(diǎn)未染，但是 d（v6，u3） ＝ 4，不能用4同時(shí)染v6和u3，所以還需要用另一種新的顏色.

類似可以證明其他的染色方式也不行.所以，χρ（D（Pn））≥ 5.

再證 χρ（D（Pn）） ≤ 5.

下面構(gòu)造一個(gè)映射 f： V（D（Pn）） → {1，2，3，4，5}.

當(dāng) i≡ 1（mod2）時(shí)， 令 f（vi）＝ 1； 當(dāng) i≡ 0（mod6）時(shí)， 令 f（vi） ＝ 5；

當(dāng) i≡ 2（mod6）時(shí)， 令 f（vi） ＝ 2； 當(dāng) i≡ 4（mod6）時(shí)， 令 f（vi） ＝ 3；

當(dāng) j≡ 0（mod2）時(shí)， 令 f（uj） ＝ 1； 當(dāng) j≡ 1（mod6）時(shí)， 令 f（uj） ＝ 3；

當(dāng) j≡ 3（mod6）時(shí)， 令 f（uj） ＝ 4； 當(dāng) j≡ 5（mod6）時(shí)， 令 f（uj） ＝ 2.

易證映射 f是 D（Pn）的一個(gè)泛寬度染色， 所以 χρ（D（Pn）） ≤ 5.

綜上， 當(dāng) n>5 時(shí)， 有 χρ（D（Pn）） =5.

注 1 特別地， 當(dāng) n=3， 4， 5 時(shí)， χρ（D（Pn）） ＝ 4.

定理 2 設(shè) Wn， W′n為兩個(gè)輪， 其頂點(diǎn)集分別為 V（Wn） ={v0，v1，v2，…，vn}和 V（W′n） ={u0，u1，u2，…，un}， 則 χρ（D（Wn））＝ n+2.

證明 首先證明 χρ（D（Wn）） ≥ n+2.

由圖D（Wn）的結(jié)構(gòu)易知，圖D（Wn）中最長(zhǎng)的是 P4，即圖D（Wn）中任意兩點(diǎn)之間的距離都小于等于3，那么最多只有顏色1和2可以染多個(gè)頂點(diǎn)，其余的顏色只能用來(lái)染一個(gè)頂點(diǎn).相互之間距離大于等于2的頂點(diǎn)構(gòu)成D（Wn）的獨(dú)立集，易知，圖D（Wn）的最多獨(dú)立集I滿足滿足任意兩點(diǎn)相互之間的距離大于等于3的頂點(diǎn)集中只有兩個(gè)頂點(diǎn)，因此需要顏色數(shù)大于等于2n+2-n-2+2=n+2，即χρ（D（Wn））≥ n+2.

再證 χρ（D（Wn））≤ n+2， 即用 n+2種顏色可以完成對(duì)圖 D（Wn）的泛寬度染色.

用1來(lái)染最大獨(dú)立集I中的頂點(diǎn)，用2來(lái)染剩余未染的并且滿足距離大于等于3的頂點(diǎn)，對(duì)于剩余的2n+2-n-2=n個(gè)頂點(diǎn)，因?yàn)橄嗷ブg的距離都小于等于3，所以n個(gè)頂點(diǎn)可以用n種染色來(lái)染，染完D（Wn）的所有頂點(diǎn)一共用了n+1+1=n+2種顏色.所以， χρ（D（Wn）） ≤ n+2.

綜上， 有 χρ（D（Wn）） ＝ n+2.

注2 圖的泛寬度染色是依據(jù)頂點(diǎn)之間的距離對(duì)頂點(diǎn)的一種剖分.對(duì)于不具有特定圖結(jié)構(gòu)的任意圖來(lái)說(shuō)，確定圖中任意兩個(gè)頂點(diǎn)的距離是非常困難的，而且目前已知的結(jié)論中，也都是針對(duì)具有具體圖結(jié)構(gòu)的圖類來(lái)研究的，并且在文獻(xiàn)［1］中作者也猜想：確定任意圖的泛寬度色數(shù)問(wèn)題是NP完備問(wèn)題.

下面構(gòu)造一個(gè)算法來(lái)實(shí)現(xiàn)對(duì)任意圖的泛寬度染色.

思想 在第i步從那些未染色的點(diǎn)中，找一個(gè)極大的i-寬度箱Xi，把Xi中所有的頂點(diǎn)染顏色i，指標(biāo)i從1開始，每一步增加1，用k表示i的最終值.

算法

從這個(gè)算法可以很容易得出，對(duì)于任意圖G，有χρ（G）≤k.在第一步中，當(dāng)i=1時(shí)，V中極大的1-寬度箱就是圖G的最大獨(dú)立子集I，即X1=I，由此可以得到：

對(duì)于很稠密的圖來(lái)說(shuō)，上述式子可以取到等號(hào)，即：

例如完全圖Kn.

3 結(jié) 語(yǔ)

本文研究了由兩條路以及兩個(gè)圈構(gòu)成的雙圖的泛寬度染色，并得出了這兩類雙圖的泛寬度色數(shù).本文的不足之處在于研究的圖類簡(jiǎn)單，只給出了在兩條路或兩個(gè)圈之間加一重匹配.可考慮加多重匹配，還可進(jìn)一步考慮研究其他圖類的泛寬度色數(shù).

[1]Bresar B,Klavzar S,Rall D F.On the packing number of cartesian products， hexagonal lattice，and trees[J]. Discrete Applied Mathematics， 2007， 155（17）： 2 303-2 311.

[2]Scoper C.An eccentric coloring of trees[J].Australasia J Combin， 2004（29）： 309-321.

[3]張姍姍，劉曉曉，陳麗華.幾類特殊圖的泛寬度色數(shù)[J].山東科學(xué)，2008，21（04）：32-37.

[4]陳麗華，張姍姍，劉曉曉.圈及其相關(guān)圖的泛寬度染色[J].山東科學(xué)，2008，21（05）：75-78.

[5]Bondy J A， Murtyu S R.Graph theory with applications[M].London： Macmillan Press， 1976， 75-128.

[6]Bollobas B.Modern graph theory[M].New York： Springer-Verlag， 1998， 145-177.

Abstract：The packing coloring， to be related to frequency assignment problem of coloring problem，were deliberated.The packing numbers of two kinds of graphs were given.

Key words：packing coloring； d-packing； packing chromatic number； double graph

On the Packing Coloring of Two Kinds of Graphs

LIU Xiu-li

（Department of Mathematics， Heze University， Heze 274015， Shandong， China）

O 157.5

A

1001-4217（2010）04-0008-04

2009-09-30

劉秀麗（1977－），女，山東曹縣人，講師，碩士研究生.研究方向：圖論與組合優(yōu)化.E-mail：liuxiuli1004@163.com