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

高 煒，梁 立，夏幼明

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

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

高 煒，梁 立，夏幼明

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

圖的著色問(wèn)題是圖論的重要研究課題之一，分?jǐn)?shù)色數(shù)作為正常色數(shù)的一個(gè)推廣在計(jì)算機(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年對(duì)圖的多重著色的研究.E.R.Scheinerman和D.H.Ullman在文獻(xiàn)[1]中有關(guān)于此專(zhuān)題的較為詳盡的論述.圖的分?jǐn)?shù)色數(shù)有著十分廣泛的應(yīng)用，例如MWIS問(wèn)題，相關(guān)內(nèi)容可參考文獻(xiàn)[1－3].關(guān)于圖的分?jǐn)?shù)著色有很多不同的定義方式，下面給出幾種最常見(jiàn)也是最重要的定義，即：分?jǐn)?shù)著色，分?jǐn)?shù)團(tuán)和a：b著色.文中只考慮無(wú)向、簡(jiǎn)單、有限圖.文中涉及的符號(hào)和標(biāo)記若沒(méi)有特別說(shuō)明，則與文獻(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中各頂點(diǎn)分配一個(gè)集合{1，2，…，a}的b元子集，使得相鄰頂點(diǎn)的集合不交，則χ（fG）=inf{a/b存在a：b著色}.

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

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

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

定義1.6圖G的關(guān)聯(lián)圖S(G)是這樣一個(gè)圖：V (S(G))={(v，e)∈V(G)，e∈E(G)且v與e在G中關(guān)聯(lián)}，頂點(diǎn)(u，e)，(v，f)之間存在邊當(dāng)且僅當(dāng)下列三種情況之一：①u(mài)=v；②e=f；③uv=e或uv=f.圖G的關(guān)聯(lián)圖的色數(shù)稱(chēng)為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)是這樣的圖：它的頂點(diǎn)集合為V(G)∪E(G)，T(G)中兩個(gè)頂點(diǎn)之間存在邊當(dāng)且僅當(dāng)它們?cè)贕中相鄰或相關(guān)聯(lián).圖G的全圖的色數(shù)稱(chēng)為G的全色數(shù)，記為χ″（G）.用χ″f（G）表示G的分?jǐn)?shù)全色數(shù)，即G的全圖的分?jǐn)?shù)色數(shù).

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

引理1.1[4]對(duì)階數(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ì)證明過(guò)程，用類(lèi)似的方法可證明定理2.1.

定理2.2證明：

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

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

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

(2)易證

3 一些推論

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

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

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

[2]高煒，梁立，夏幼明.兩種特殊冠圖的相關(guān)分?jǐn)?shù)色數(shù)研究[J].西安文理學(xué)院學(xué)報(bào)：自然科學(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é)報(bào)：自然科學(xué)版，2008，28(1)：31-33.

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

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

[8]馮愛(ài)芬，王秀梅，王鋒葉.幾類(lèi)特殊圖的樹(shù)寬[J].洛陽(yáng)師范學(xué)院學(xué)報(bào)，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

〔編輯 高?！?/p>

1674-0874(2010)01-0012-03

2009-10-13

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

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