MWIS問(wèn)題模型中幾類圖形的分?jǐn)?shù)色數(shù)

1、MWIS問(wèn)題模型中幾類圖形的分?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)用,例如MWIS問(wèn)題.給出了齒頂邊星圖、蛛網(wǎng)圖以及它們的r-冠圖的分?jǐn)?shù)色數(shù)、分?jǐn)?shù)關(guān)聯(lián)色數(shù)和分?jǐn)?shù)全色數(shù).關(guān)鍵詞：分?jǐn)?shù)色數(shù)；分?jǐn)?shù)團(tuán)；分?jǐn)?shù)關(guān)聯(lián)色數(shù); 分?jǐn)?shù)全色數(shù); 星極圖中圖分類號(hào): TQ92 文獻(xiàn)標(biāo)識(shí)碼： A1 基本概念和引理 與圖的分?jǐn)?shù)著色有關(guān)的研究最早可以追溯到1970年對(duì)圖的多重著色的研究. E.R.Scheinerman和D.H.Ullman在1中有關(guān)于此專題的較為

2、詳盡的論述. 圖的分?jǐn)?shù)色數(shù)有著十分廣泛的應(yīng)用, 例如MWIS問(wèn)題. 處理這個(gè)問(wèn)題的模型是無(wú)向圖G = (V, E) . 圖中每個(gè)頂點(diǎn)表示一臺(tái)處理器,頂點(diǎn)與頂點(diǎn)之間存在邊當(dāng)且僅當(dāng)頂點(diǎn)所代表的處理器之間有共享的資源. MWIS問(wèn)題等價(jià)于分?jǐn)?shù)著色問(wèn)題.研究特殊圖形的分?jǐn)?shù)色數(shù)有助于解決特殊多處理器結(jié)構(gòu)下的MWIS問(wèn)題,相關(guān)內(nèi)容可參考2,3. 關(guān)于齒頂邊星圖(m1,m2,mn),蛛網(wǎng)圖W(m,n) 的定義可參考4,5,6. 在G的r-冠圖中,頂點(diǎn)v上粘接的r條懸掛邊的端點(diǎn)集記作v*. (本文只考慮無(wú)向、簡(jiǎn)單、有限圖.文中涉及的符號(hào)和標(biāo)記若沒(méi)有特別說(shuō)明,則與7一致)2.主要定理以及證明本文給出了齒頂邊星圖

3、、蛛網(wǎng)圖以及它們的r-冠圖的幾種分?jǐn)?shù)色數(shù)如下：定理2.1 f (m1,m2,mn)=2; incf (m1,m2,mn)=maxn+1, +3; (m1,m2,mn)= maxn+1, +3.定理2.2 f ()=; incf ()=; ()=.定理2.3 f (W(m,n)= ; incf (W(m,n)= ; ( W(m,n)=.定理2.4f (Ir(m1,m2,mn)=2; incf (Ir(m1,m2,mn)=maxn+r+1,+r+3; (Ir(m1,m2,mn)=maxn+r+1, +r+3.定理2.5f (Ir()=; incf (Ir()= ;(Ir()=2m+r+1.定理2.

4、6f (Ir(W(m,n)=; incf (Ir(W(m,n)= ; (Ir(W(m,n)= . 由于篇幅有限,這里只給出定理2.6的詳細(xì)證明過(guò)程,用類似的方法可證明其他結(jié)論.定理2.6證明: (1)當(dāng)n為偶數(shù)時(shí),一方面Ir(W(m,n)中存在K3,由f (K3 )=3知(Ir(W(m,n)3.另一方面,在W(m,n)中記從內(nèi)到外第j(1jm)個(gè)圈相對(duì)應(yīng)的n個(gè)頂點(diǎn)為 uj1,uj2,ujn; 相對(duì)應(yīng)的n個(gè)外部懸掛點(diǎn)為 t1,t2,tn; 中心頂點(diǎn)為x. 對(duì)于uji (1jm, 1in),若i+j=奇數(shù),則著顏色1.若i+j=偶數(shù),則著顏色2; t1,t2,tn和中心頂點(diǎn)x著顏色3. 中頂點(diǎn)均著

5、顏色3; , , 和中頂點(diǎn)均著顏色1或2.從而Ir(W(m,n)存在正常3著色,即(Ir(W(m,n)3. 故有( Ir(W(m,n)=3.當(dāng)n為奇數(shù)時(shí),構(gòu)造Ir(W(m,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分別分配

6、子集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; t1,t2,tn和中心頂點(diǎn)x均分配2n+1,2n+2,3n-1; 中頂點(diǎn)分配2n+1,2n+2,3n-1; , , 和中頂點(diǎn)可分配1,2,2n中的任意n-1個(gè)元素.由定義,這就是Ir(W(m,n)的(3n-1):(n-1)著色.從而f(Ir(W(m,n).另一方面,構(gòu)造Ir(W(m,n)的分?jǐn)?shù)團(tuán)g,使得=:對(duì)任意yu11, u12,u1n,有g(shù)(y)=;若y=x,有g(shù)(y)=1;若yV(Ir(W(m,n)- x, u11, u12,u1n,有g(shù)(y)=0.下

7、面證明對(duì)任意Ir(W(m,n)中的極大獨(dú)立集S,有1(所謂極大獨(dú)立集S是指,對(duì)于任意yV(Ir(W(m,n)且yS,有Sy不是獨(dú)立集).由g的定義可知,要使的值最大,獨(dú)立集中要盡可能多地包含最內(nèi)圈中頂點(diǎn)或包含頂點(diǎn)x.若S中包含x, 則S不包含最內(nèi)圈中任何頂點(diǎn),從而有=1;若S中存在最內(nèi)圈中頂點(diǎn),則S包含該圈的最大獨(dú)立集但不包含x.由于長(zhǎng)為n的奇圈的最大獨(dú)立集基數(shù)為,從而有 =1.所以對(duì)任意Ir(W(m,n)中的極大獨(dú)立集S,有1.從而對(duì)任意Ir(W(m,n)中的獨(dú)立集S,有1.根據(jù)定義,g是Ir(W(m,n)的分?jǐn)?shù)團(tuán).從而有f(Ir(W(m,n) =.綜合上述兩方面,當(dāng)n為奇數(shù)時(shí),f(Ir(W

8、(m,n)=.(2)設(shè)中的頂點(diǎn)分別是x1,x2, xr,相對(duì)應(yīng)的各條懸掛邊分別記為e1,e2, ,er;邊xu11,xu12, xu1n分別記為e1, e2, en. 顯然有(S(Ir(W(m,n)= . 從而incf (Ir(W(m,n) .下面證明inc(Ir(W(m,n)= .定義:圖G的關(guān)聯(lián)圖S(G)的某個(gè)正常著色具有性質(zhì)P,是指:yV(G),設(shè)NG(y)=y1,y2,yk,則(y1,y1 y),( y2, y2 y),( yk, yk y)著相同的顏色. 當(dāng)n=3時(shí),首先用6種(因?yàn)閞1,因此當(dāng)n=3時(shí),r+56)顏色著S(W(m,3),并且在不考慮中心頂點(diǎn)x的情況下,使該著色具有性

9、質(zhì)P: (x,e1),(x,e2),(x,e3)分別著1,2,3; (u11,e1),(u12,e2)著4;(u13,e3)著6;( u11, u11u12), ( u12, u11u12), ( u12, u12u13), ( u13, u12u13), ( u13, u13u11), ( u11, u13u11)分別著2,1,3,2,1,3; ( u11, u11u21), ( u12, u12u22), ( u13, u13u23)分別著5,6,4; ( u21, u11u21), ( u22, u12u22), ( u23, u13u23)分別著1,2,3.( u22, u21u22)

10、 , ( u23, u23u21), ( u31, u31u21)均著5; ( u21, u21u22) , ( u23, u23u22), ( u32, u32u22)均著6; ( u21, u21u23) , ( u22, u23u22), ( u33, u33u23)均著4; ( u21, u21u31)著2,( u32, u32u31), ( u33, u33u31)著2;( u22, u22u32)著3, ( u23, u23u33)著1; ( u31, u31u32), ( u33, u33u32)著3; ( u31, u31u33), ( u32, u33u32)著1;( u31

11、, u31u41)著 4, ( u51, u51u41), ( u42, u42u41), ( u43, u43u41)著4; ( u32, u32u42), ( u41, u41u42), ( u43, u43u42), ( u52, u52u42)著 5; ( u33, u33u43), ( u41, u41u43) ,( u42, u43u43) ,( u53, u53u43)著 6;(u41, u41u51)著 1, ( u61, u61u51), ( u52, u52u51), ( u53, u53u51)著1; ( u42, u42u52), ( u51, u51u52), ( u

12、53, u53u52), ( u62, u62u52)著 2; ( u43, u43u53), ( u51, u51u53) ,( u52, u52u53) ,( u63, u63u53)著 3; ( u51, u51u61)著 1, ( u71, u71u61), ( u62, u62u61), ( u63, u63u61)著5; ( u52, u52u62), ( u61, u61u62), ( u63, u63u62), ( u72, u72u62)著 6; ( u53, u53u63), ( u61, u61u63) ,( u62, u62u63) ,( u73, u73u63)著 4

13、.我們發(fā)現(xiàn),第6圈的著色和第2圈是一樣的,因此第7圈的著色可與第3圈一樣, ,以此構(gòu)成循環(huán),可以一直著下去. 其次,將S(W(m,3)的6著色推廣到S(Ir(W(m,3).對(duì)于W(m,3)的中心頂點(diǎn)x而言,(x, e1),(x,e2),(x, er)分別著5,7,8,r+5;而(x1, e1),( x2,e2), (xr, er)可著4或6;對(duì)于uji,設(shè)在S(W(m,3)中包含在W(m,3)中與uji關(guān)聯(lián)的4條邊的頂點(diǎn)的顏色集為Uji，則=5.設(shè)中元素分別為,則(uji, uji), (uji,uji),(uji, uji)分別各著集合1,2,r+5-Uji中的一種顏色,而(, uji),

14、(,uji),(, uji)均著與在S(W(m,3)中包含在W(m,3)與uji相關(guān)聯(lián)的邊和相鄰的頂點(diǎn)所組成的頂點(diǎn)一樣的顏色. 例如:對(duì)于點(diǎn)u11,頂點(diǎn)(x,e1), ( u12, u11u12), ( u13, u13u11), ( u21, u11u21)所著的顏色均為1，則(, u11), (,u11),(, u11)均著1.用同樣的方法可處理與t1,t2,t3相關(guān)的頂點(diǎn)的著色.從而S(Ir(W(m,3)是r+5可著色的. 當(dāng)n=4,m2時(shí),S(W(m,4)可用5種顏色正常著色, 且使著色具有性質(zhì)P: (x,ei)著i(1i4); (u1i,ei)著5 i(1i4);從而(u12, u1

15、2u11) ,(u14, u14u11) ,(u21, u11u21)著1; (u13, u12u13) ,(u11, u12u11) ,(u22, u12u22)著2;(u12, u12u13), (u14, u14u13) ,(u23, u13u23)著3;(u11, u14u11) ,(u13, u14u13), (u24, u14u24)著4;因此(u11, u21u11), (u22, u22u21) ,(u24, u24u21),(t1,t1u21)著3; (u12, u22u12), (u21, u22u21) ,(u23, u23u22),(t2,t2u22)著4;(u13,

16、u23u13), (u22, u22u23) ,(u24, u24u23),(t3,t3u23)著1; (u14, u24u14), (u21, u24u21) ,(u23, u24u23),(t4,t4u24)著2; (u21,t1u21), (u22,t2u22), (u23,t3u23), (u24,t4u24)著5. 類似n=3的討論,可知該S(W(m,4)的5著色可推廣到S(Ir(W(m,4)的r+5著色. 當(dāng)n=4,r2 m3時(shí), n+r+17,下面給出S(W(m,4)的滿足性質(zhì)P的正常7著色: (x,ei)著i(1i4); (u1i,ei)著5 (1i4);從而(u12, u12

17、u11) ,(u14, u14u11) ,(u21, u11u21)著1; (u13, u12u13) ,(u11, u12u11) ,(u22, u12u22)著2;(u12, u12u13), (u14, u14u13) ,(u23, u13u23)著3;(u11, u14u11) ,(u13, u14u13), (u24, u14u24)著4; (u11, u21u11), (u22, u22u21) ,(u24, u24u21),( u31, u31u21)著3; (u12, u22u12), (u21, u22u21) ,(u23, u23u22),( u32, u32u22)著6;

18、(u13, u23u13), (u22, u22u23) ,(u24, u24u23),(u33, u33u23)著1; (u14, u24u14), (u21, u24u21) ,(u23, u24u23),( u34, u34u24)著7; (u21, u21u31), (u32, u32u31) ,(u34, u34u31),( u41, u31u41)著5; (u22, u22u32), (u31, u32u31) ,(u33, u33u32),( u42, u42u32)著4; (u23, u23u33), (u32, u32u33) ,(u34, u34u33),(u43, u33

19、u43)著2; (u24, u24u34), (u31, u34u31) ,(u33, u34u33),( u44, u34u44)著6;(u31, u41u31), (u42, u42u41) ,(u44, u44u41),( u51, u51u41)著1; (u32, u42u32), (u41, u42u41) ,(u43, u43u42),( u52, u52u42)著7; (u33, u43u33), (u42, u42u43) ,(u44, u44u33),(u53, u53u43)著3; (u34, u34u44), (u41, u44u41) ,(u43, u44u43),(

20、u54, u54u44)著4;(u41, u41u51), (u52, u52u51) ,(u54, u54u51),( u61, u61u51)著3; (u42, u42u52), (u51, u52u51) ,(u53, u53u52),( u62, u62u52)著6; (u43, u43u53), (u52, u52u53) ,(u54, u54u53),(u63, u63u53)著1; (u44, u54u44), (u51, u54u51) ,(u53, u54u53),( u64, u54u64)著7;(u51, u61u51), (u62, u62u61) ,(u64, u64

21、u61),( u71, u61u71)著5; (u52, u62u52), (u61, u62u61) ,(u63, u63u62),( u72, u62u72)著4; (u53, u53u63), (u62, u62u63) ,(u64, u64u63),(u73, u63u73)著2; (u54, u54u64), (u61, u64u61) ,(u63, u64u63),( u74, u74u64)著6;(u61, u61u71),著1; (u62, u62u72)著7; (u63, u63u73)著3; (u64, u64u74)著4.由此,我們發(fā)現(xiàn)第6層相關(guān)頂點(diǎn)的著色和第3層完全一致

22、,從而得到一個(gè)循環(huán),第7層的相關(guān)著色和第4層一致, 第8層的相關(guān)著色和第5層一致, .這就是S(W(m,4)的滿足性質(zhì)P的正常7著色類似n=3的討論,可知該S(W(m,4)的7著色可推廣到S(Ir(W(m,4)的r+5著色.當(dāng)n5時(shí),首先用n+1種顏色著S(W(m,n),并使得著色具有性質(zhì)P.方法如下(設(shè)該著色為):(x,ei)=i(1in); (u11,e1)=( u12,e2)=(u1n,en)=n+1.從而(u12, u11u12)= (u1n, u11u1n)=(u21, u11u21)=1;(u11, u11u12)=(u13, u12u13)=(u22, u12u22)=2; ;

23、(u11, u11u1n)=(u1(n-1), u1(n-1)u1n)=(u2n, u1nu2n)=n; (u1i, u1i u2i)= (x,ei)+2(mod n); (uji, uji u(j+1)i)= ( u(j-1)i, u(j-1)i uji)+2 (mod n)(2jm); ( u(j+1)i, uji u(j+1)i)= ( uji, u(j-1)i uji)+2 (mod n)(2jm); (uji, uji uj(i+1)=(u(j-1)i, u(j-1)i u(j-1)(i+1)+2 (mod n); (uji, uji uj(i-1)=(u(j-1)i, u(j-1)

24、i u(j-1)(i-1)+2 (mod n); (umi, umi ti)=(u(m-1)i, u(m-1)i umi)+2 (mod n); ( ti, umi ti)=(umi, u(m-1)i umi)+2 (mod n).下面證明,這就是S(W(m,n)的n+1正常著色且具有性質(zhì)P.觀察即知,對(duì)W(m,n)中的頂點(diǎn)u1i來(lái)說(shuō),(x,xu1i),( u1(i+1), u1(i+1) u1i) ,( u1(i-1), u1(i-1) u1i) ,( u2i, u2iu1i)所著顏色相同.而對(duì)于uji(2jm)來(lái)說(shuō),由于每一層的相關(guān)元素的色數(shù)為上一層加2,因此和uji相鄰的點(diǎn)和相關(guān)聯(lián)的邊構(gòu)

25、成的S(W(m,n)中的頂點(diǎn)所著的顏色相同.所以只需說(shuō)明是正常著色即可.直接觀察可知,第一層著色是正常的.由于著色是每一層對(duì)應(yīng)元素加2(mod n),因此只需驗(yàn)證第2層即可.對(duì)于W(m,n)中的頂點(diǎn)u2i,(u2i,u2(i+1)u2i)與10個(gè)頂點(diǎn)相鄰,它們是(u1i,u1iu2i), ( u2i,u2iu1i), (u2(i-1), u2(i-1)u2i),(u2i,u2(i-1)u2i), (u3i,u3iu2i), (u2i,u3iu2i), (u2(i+1),u2(i+1)u2i) , (u2(i+1),u2(i+1) u2(i+2), (u2(i+1),u2(i+1) u1(i+1

26、) ,( u2(i+1),u2(i+1) u3(i+1).其中(u1i,u1iu2i), (u2(i-1), u2(i-1)u2i), (u3i,u3iu2i), (u2(i+1),u2(i+1)u2i)著相同的顏色i+2;( u2i,u2iu1i)著顏色i; (u2i,u3iu2i)與(u2(i+1),u2(i+1) u2(i+2),著相同的顏色i+4; (u2i,u2(i-1)u2i)和 (u2(i+1),u2(i+1) u1(i+1)著i+1; ( u2(i+1),u2(i+1) u3(i+1)著i+5.從而這10條邊一共著5種顏色i,i+1, i+2, i+4, i+5 (mod n)

27、.而(u2i,u2(i+1)u2i)本身著i+3 (mod n)，因此(u2i,u2(i+1)u2i)不和它的鄰邊著相同的顏色.同理, (u2i,u2(i-1)u2i)也不和它的鄰邊著相同的顏色.另外與( u2i,u2iu1i)相鄰的10條邊著i+1, i+2, i+3, i+4, n+1(當(dāng)j3時(shí)該值為i-2), i-1,6種顏色,而( u2i,u2iu1i)本身著顏色i,所以( u2i,u2iu1i)不和相鄰的邊著相同的顏色(著相同顏色的兩條邊的顏色差為0或n的整數(shù)倍,但n5). 與(u2i,u3iu2i)相鄰的10條邊著i,i+1, i+2,i+3,i+5,i+6,而(u2i,u3iu2

28、i)本身著i+4,所以(u2i,u3iu2i)不和相鄰的邊著相同的顏色.因此與W(m,n)中第二層頂點(diǎn)相關(guān)的S(W(m,n)中的頂點(diǎn)著色正常.從而是S(W(m,n)的正常n+1著色. 類似n=3的討論,可知該S(W(m,n)的n+1著色可推廣到S(Ir(W(m,n)的n+r+1著色. 從而incf (Ir(W(m,n) . 故incf (Ir(W(m,n)= .(3) 顯然有(T(Ir(W(m,n)= .從而(Ir(W(m,n) . 下面證明(Ir(W(m,n)= .當(dāng)n=3時(shí),首先給出T(W(m,3)的5著色如下: (x)= ( u11u21)=1, (e1)=(u13)= ( u12u22

29、)= (u21)=2, (e2)=( u11)=( u13u23)= (u22)=3,(e3)= (u23)=4,(u12)=5, (uj1uj2)=4 (1jm), (uj2uj3)=1(1jm),(uj3uj1)=5(1jm), (uji)= ( u(j-1)i u(j-2)i) (1i3, 3jm),( uji u(j-1)i)= (u(j-2)i) (1i3, 3jm).最后, (ti)= (umiu(m-1)i); (tiumi)= (u(m-1)i). 從而由內(nèi)到外,可得到T(W(m,n)的5著色.其次, T(W(m,3)的5著色可擴(kuò)展到T(Ir(W(m,3)的r+5著色:對(duì)于W(

30、m,3)中任意一點(diǎn)的r條懸掛邊可分別著與該點(diǎn)和該點(diǎn)關(guān)聯(lián)邊不同的顏色,對(duì)于該點(diǎn)的r個(gè)懸掛點(diǎn)可著與該點(diǎn)在W(m,3)中的某一條關(guān)聯(lián)邊相同的顏色.當(dāng)n4時(shí),首先給出T(W(m,n)的n+1著色如下: (x)=n+1;(ei)=i(1in); (u1i)=i+1(mod n)(1in); (ujiuj(i+1)=i-1 (mod n) (1jm,1in); (u1iu2i)=n+1(1in);(u2i) =i (1in);繼續(xù)擴(kuò)展: (ujiu(j+1)i)= (u(j-1)i) (2jm,1in); (uji)= (u(j-1)iu(j-2)i) (3jm,1in); (ti)= (umiu(m-1

31、)i); (tiumi)= (u(m-1)i).易證,可將T(W(m,n)的n+1著色擴(kuò)展到T(Ir(W(m,n)的n+r+1著色.從而(Ir(W(m,n) . 故(Ir(W(m,n)= . (證畢)3.一些推論根據(jù)以上得到的結(jié)論再結(jié)合分?jǐn)?shù)色數(shù)與圓色數(shù)的關(guān)系,我們得到如下推論:推論3.1 (m1,m2,mn)=(m1,m2,mn)=2;(S(m1,m2,mn)= (S(m1,m2,mn) = maxn+1, +3;(T(m1,m2,mn)= (T(m1,m2,mn) = maxn+1, +3.推論3.2 ()=()=2 (n為偶數(shù)); (S()=(S()=2m+1(m2或m=1, n=3k);

32、 (T()=(T()=2m+1(m2或m=1, n=3k).推論3.3 (W(m,n)=(W(m,n)= 3(n為偶數(shù)); (S(W(m,n)=(S(W(m,n)= ; (T(W(m,n) =(T( W(m,n) =.推論3.4(Ir(m1,m2,mn)=(Ir(m1,m2,mn)=2; (S(Ir(m1,m2,mn)= (S(Ir(m1,m2,mn)= maxn+r+1,+r+3;(T(Ir(m1,m2,mn)= (T(Ir(m1,m2,mn)= maxn+r+1,+r+3.推論3.5(Ir()=(Ir()=2 (n為偶數(shù));(S(Ir()=(S(Ir()=2m+r+1 (m=1, n=5,

33、 r=1不同時(shí)成立);(T(Ir()=(T(Ir()=2m+r+1.推論3.6(Ir(W(m,n)=(Ir(W(m,n)=3(n為偶數(shù)); (S(Ir(W(m,n)=(S(Ir(W(m,n)= ; (T(Ir(W(m,n)=(T(Ir(W(m,n)= .注:推論中所述所有圖形均為星極圖.4.遺留問(wèn)題本文主要研究了若干具有特殊結(jié)構(gòu)圖形的分?jǐn)?shù)色數(shù),從而為解決MWIS問(wèn)題提供了理論依據(jù).但根據(jù)以上得到的結(jié)論,對(duì)于蛛網(wǎng)圖及其r-冠圖,還有如下兩個(gè)問(wèn)題沒(méi)有解決:（1）n=3,m2以及n=4, m3時(shí)W(m,n)的分?jǐn)?shù)色數(shù)是多少？（2）n=4,r=1, m3時(shí)Ir(W(m,n)的分?jǐn)?shù)色數(shù)是多少？這兩個(gè)問(wèn)題有待進(jìn)一步研究.參考文獻(xiàn):1. Fractional Graph TheoryM. John Wiley and Sons, Inc.New York,1997.2高煒,梁立,張超. 超圖的分?jǐn)?shù)著色研究J. 云南師范大學(xué)學(xué)報(bào)(自然科學(xué)版). 2009, 29(1): 33-36.3高煒,梁立,夏幼明. 幾種特殊圖形的分?jǐn)?shù)色數(shù)研究J. 山西師范大學(xué)學(xué)報(bào)(自然科學(xué)版). 2008,22(4):16-20.4劉玉記. 一類圖的優(yōu)美性J. 四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版). 1995, 18(2):52-60.5卜長(zhǎng)江,高振濱. 網(wǎng)圖F (m , n1, n2, , nm )