球面經(jīng)緯線圖的分?jǐn)?shù)色數(shù)

高 煒，梁 立，夏幼明

(云南師范大學(xué)計算機(jī)科學(xué)與信息技術(shù)學(xué)院，云南昆明 650092）

球面經(jīng)緯線圖的分?jǐn)?shù)色數(shù)

高 煒，梁 立，夏幼明

(云南師范大學(xué)計算機(jī)科學(xué)與信息技術(shù)學(xué)院，云南昆明 650092）

圖的著色問題是圖論的重要研究課題之一，分?jǐn)?shù)色數(shù)作為正常色數(shù)的一個推廣在計算機(jī)的許多領(lǐng)域中有著重要的應(yīng)用.本文給出了球面經(jīng)緯線圖以及它的r-冠圖的分?jǐn)?shù)色數(shù)，分?jǐn)?shù)關(guān)聯(lián)色數(shù)和分?jǐn)?shù)全色數(shù).

分?jǐn)?shù)色數(shù) 分?jǐn)?shù)團(tuán) 球面經(jīng)緯線圖 分?jǐn)?shù)關(guān)聯(lián)色數(shù) 分?jǐn)?shù)全色數(shù)

與圖的分?jǐn)?shù)著色有關(guān)的研究最早可以追溯到1970年對圖的多重著色的研究.E.R.Scheinerman和D.H.Ullman在文獻(xiàn)[1]中有關(guān)于此專題的較為詳盡的論述.圖的分?jǐn)?shù)色數(shù)有著十分廣泛的應(yīng)用，例如MWIS問題，相關(guān)內(nèi)容可參考文獻(xiàn)[1－3].關(guān)于圖的分?jǐn)?shù)著色有很多不同的定義方式，下面給出幾種最常見也是最重要的定義，即：分?jǐn)?shù)著色，分?jǐn)?shù)團(tuán)和a：b著色.文中只考慮無向、簡單、有限圖.文中涉及的符號和標(biāo)記若沒有特別說明，則與文獻(xiàn)[4]一致.

1 基本概念和引理

注：定義1.1和定義1.2中S={S1，S2，…，St}，其中t=F(G)-1，即t為G的Fibonacci數(shù)減1，相關(guān)內(nèi)容可參考文獻(xiàn)[5].

定義1.3[6]圖G的a：b著色，就是指給G中各頂點分配一個集合{1，2，…，a}的b元子集，使得相鄰頂點的集合不交，則χ（fG）=inf{a/b存在a：b著色}.

以上3個定義是等價的，并且圖G的分?jǐn)?shù)色數(shù)是一個有理數(shù)，相關(guān)內(nèi)容可參考文獻(xiàn)[6].

定義1.4[7]令k和d是正整數(shù)，使得k≥2d，圖G=(V，E)的一個(k，d)著色是一個映射c：V(G)→Zk={1，2，…，k}，使得對任意的uv∈E(G)，k－dc（u）－c（v）d.由此定義圖的圓色數(shù)χ（cG）=min{k/ d有(k，d)著色}.圓色數(shù)又稱為星色數(shù)，記為χ*（G）.若圖G滿足χ（fG）=χ（cG），則G稱為星極圖(star-extremal).

定義1.5[8]球面經(jīng)緯線圖由兩個頂點u，v(稱作兩極)和連接u，v的n條經(jīng)線和球面上的m條緯線構(gòu)成，記作Cm，n.它的頂點集包括u，v和mn個內(nèi)點，每條經(jīng)線是一長度為m+1的連接u，v的路，每條緯線是一長度為n的圈，其中m≥1，n≥3.

定義1.6圖G的關(guān)聯(lián)圖S(G)是這樣一個圖：V (S(G))={(v，e)∈V(G)，e∈E(G)且v與e在G中關(guān)聯(lián)}，頂點(u，e)，(v，f)之間存在邊當(dāng)且僅當(dāng)下列三種情況之一：①u=v；②e=f；③uv=e或uv=f.圖G的關(guān)聯(lián)圖的色數(shù)稱為G的關(guān)聯(lián)色數(shù)，記為inc(G).用incf(G)表示G的分?jǐn)?shù)關(guān)聯(lián)色數(shù)，即G的關(guān)聯(lián)圖的分?jǐn)?shù)色數(shù).

定義1.7圖G=(V，E)的全圖T(G)是這樣的圖：它的頂點集合為V(G)∪E(G)，T(G)中兩個頂點之間存在邊當(dāng)且僅當(dāng)它們在G中相鄰或相關(guān)聯(lián).圖G的全圖的色數(shù)稱為G的全色數(shù)，記為χ″（G）.用χ″f（G）表示G的分?jǐn)?shù)全色數(shù)，即G的全圖的分?jǐn)?shù)色數(shù).

定義1.8圖Ir(G)表示G的r-冠圖，它是在圖G的每個頂點上都粘接r條懸掛邊所得到的圖，1-冠圖也稱為王冠.在G的一個頂點v上粘接的r條懸掛邊的端點集記作v*.

引理1.1[4]對階數(shù)為n的完全圖Kn有χf(Kn)=n.

引理1.2[4]如果H是G的子圖，則χf(H)≤χf(G).

2 主要定理以及證明

本文給出了球面經(jīng)緯線圖以及它的r-冠圖的幾種分?jǐn)?shù)色數(shù)：

由于篇幅有限，這里只給出定理2.2的詳細(xì)證明過程，用類似的方法可證明定理2.1.

定理2.2證明：

(1)當(dāng)n為偶數(shù)時，一方面Ir(Cm，n)中存在K3，由引理1.1知 χf(K3)=3，再由引理1.2知χf(Ir(Cm，n))≥3.另一方面，在Cm，n中記上往下第j(1≤j≤m)條緯線相對應(yīng)的n個頂點為 uj1，uj2，…，ujn.對于uji(1≤j≤m，1≤i≤n)，若i+j=奇數(shù)，則著顏色1.若i+j=偶數(shù)，則著顏色2；兩極u，v著顏色3.中頂點均著顏色3；u*和v*中頂點著顏色1或2.從而Ir(Cm，n)存在正常3著色，由引理1.3可知χf(Ir(Cm，n))≤3.故有 χf(Ir(Cm，n))=3.

當(dāng)n為奇數(shù)時，構(gòu)造Ir(Cm，n)的(3n-1)：(n-1)著色.對于集合{1，2，…，3n-1}，當(dāng)j為奇數(shù)時，頂點uj1，uj2，…，ujn分別分配子集{1，2，…，n-1}，{n，…，2n-2}，{2n-1，2n，1，2，…，n-3}，{n-2，n-1，…，2n-4}，…，{n+4，…，2n，1，2}，{3，…，n，n+1}，{n+2，…，2n}.也就是說，用前2n個元素的集合{1，2，…，2n}循環(huán)分配給uj1，uj2，…，ujn.每個頂點分配n-1個元素；當(dāng)j為偶數(shù)時，頂點uj1，uj2，…，ujn分別分配子集{n，…，2n-2}，{2n-1，2n，1，2，…，n-3}，{n-2，n-1，…，2n-4}，…，{3，…，n，n+1}，{n+2，…，2n}，{1，2，…，n-1}；u，v和中頂點均分配{2n+1，2n+2，…，3n-1}；u*和v*中頂點可分配{1，2，…，2n}中的任意n-1個元素.由定義，這就是Ir(Cm，n)的(3n-1)：(n-1)著色.從而

綜合上述兩方面，當(dāng)n為奇數(shù)時，

(2)易證

3 一些推論

根據(jù)以上得到的結(jié)論再結(jié)合引理1.3，我們得到如下推論：

注：推論中所述所有圖形均為星極圖.

[1]高煒，梁立，張超.超圖的分?jǐn)?shù)著色研究[J].云南師范大學(xué)學(xué)報：自然科學(xué)版，2009，29(1)：33-36.

[2]高煒，梁立，夏幼明.兩種特殊冠圖的相關(guān)分?jǐn)?shù)色數(shù)研究[J].西安文理學(xué)院學(xué)報：自然科學(xué)版，2009，12(1)：27-30.

[3]Bondy JA，Murty U SR.Graph theory with applications[M].New York：Macmillan Press Lid，1976.

[4]Scheinerman E R，Ullman D H.Fractional Graph Theory[M].New York：John Wiley and Sons，1997.

[5]高煒.隨機(jī)圖的Fibonacci數(shù)研究[J].云南師范大學(xué)學(xué)報：自然科學(xué)版，2008，28(1)：31-33.

[6]晏靜之.關(guān)于某些圖類的分?jǐn)?shù)色數(shù)[D].蘭州：西北師范大學(xué)，2004.

[7]Vince A.Star Chromatic Number[J].Graph Theory，1988，12：551-559.

[8]馮愛芬，王秀梅，王鋒葉.幾類特殊圖的樹寬[J].洛陽師范學(xué)院學(xué)報，2004(2)：7-9.

Fractional C hromatic N umber of M eridian and L atitude L ines on a S phere

GAOWei，LIANG Li，XIA You-ming
(School of Computer Science and Information Technology，Yunnan Normal University，Kunming Yunnan，650092)

The issue of coloring is a very important in the graph theory.Fractional coloring as generalized coloring has used in many fields of computer science.This paper gives formulas to compute the fractional chromatic number、fractional incidence chromatic number and fractional total chromatic number ofmeridian and latitude lines on a sphere and its r-corona graph.

f ractional chromatic number；f ractional clique；meridian and latitude lines on a sphere；f ractional incidence chromatic number；f ractional total chromatic number

TQ92

A

〔編輯 高海〕

1674-0874(2010)01-0012-03

2009-10-13

國家自然科學(xué)基金項目［60903131］；云南省教育廳科研基金項目［07Z40092］

高煒(1981-)，男，浙江紹興人，碩士，研究方向：圖論及其應(yīng)用.