1、作者简介: 高炜(1981-),男,浙江绍兴人,硕士,主要从事图论及其应用研究. 通讯作者：梁立(1965-),男,重庆市潼南县人,教授,硕士生导师,主要从事图论、智能决策支持系统的研究.项目基金: 国家自然科学基金项目（60903131） ；云南省教育厅科研基金项目(07Z40092)MWIS 问题模型中几类图形的分数色数高炜 梁立 * 夏幼明(云南师范大学计算机科学与信息技术学院,云南 昆明 650092)摘要：图的着色问题是图论的重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用,例如 MWIS 问题.给出了齿顶边星图、蛛网图以及它们的 r-冠图的分数色数
2、、分数关联色数和分数全色数 .mnC关键词：分数色数；分数团；分数关联色数; 分数全色数 ; 星极图中图分类号: TQ92 文献标识码： A1 基本概念和引理与图的分数着色有关的研究最早可以追溯到 1970 年对图的多重着色的研究. E.R.Scheinerman 和 D.H.Ullman 在1中有关于此专题的较为详尽的论述 . 图的分数色数有着十分广泛的应用, 例如 MWIS 问题. 处理这个问题的模型是无向图 G = (V, E) . 图中每个顶点表示一台处理器,顶点与顶点之间存在边当且仅当顶点所代表的处理器之间有共享的资源. MWIS 问题等价于分数着色问题.研究特殊图形的分数色数有助于
3、解决特殊多处理器结构下的 MWIS 问题 ,相关内容可参考 2,3. 关于齿顶边星图 (m1,m2,mn), ,蛛网图 W(m,n) nWC的定义可参考4,5,6. 在 G 的 r-冠图中,顶点 v 上粘接的 r 条悬挂边的端点集记作 v*. (本文只考虑无向、简单、有限图.文中涉及的符号和标记若没有特别说明,则与7一致)2.主要定理以及证明本文给出了齿顶边星图、 、蛛网图以及它们的 r-冠图的几种分数色数如下：mnC定理 2.1 f ( (m1,m2,mn)=2; incf ( (m1,m2,mn)=maxn+1, +3;nWnW( (m1,m2,mn)= maxn+1, +3.fn 定理
4、2.2 f ( )= ; incf ( )= ; mnC为 奇 数为 偶 数,12mnCknmkk3,12,123,或( )= .fmnCknmkk3,12,123,或2定理 2.3 f (W(m,n)= ; incf (W(m,n)= 为 奇 数为 偶 数,13; ( W(m,n)= .5,12,4,n或 f4,135定理 2.4 f (Ir( (m1,m2,mn)=2; incf (Ir( (m1,m2,mn)=maxn+r+1, +r+3;n n (Ir( (m1,m2,mn)=maxn+r+1, +r+3.fW定理 2.5 f (Ir( )= ; incf (Ir( )= nC为 奇
5、数为 偶 数,1mnC; (Ir( )=2m+r+1.的 其 他 情 况或2,12,5,3mrrfn定理 2.6 f (Ir(W(m,n)= ; incf (Ir(W(m,n)= 为 奇 数为 偶 数,13; (Ir(W(m,n)= . 2,342,45,1rnrn或或 f4,135nr由于篇幅有限,这里只给出定理 2.6 的详细证明过程,用类似的方法可证明其他结论.定理 2.6 证明: (1)当 n 为偶数时 ,一方面 Ir(W(m,n)中存在 K3,由 f (K3 )=3 知 (Ir(W(m,n)f3.另一方面,在 W(m,n)中记从内到外第 j(1 j m)个圈相对应的 n 个顶点为 u
6、j1,uj2,ujn; 相对应的 n 个外部悬挂点为 t1,t2,tn; 中心顶点为 x. 对于 uji (1 j m, 1 i n),若 i+j=奇数,则着颜色 1.若 i+j=偶数,则着颜色 2; t1,t2,tn 和中心顶点 x 着颜色 3. 中顶点均着颜色 3; , *ji *1t, 和 中顶点均着颜色 1 或 2.从而 Ir(W(m,n)存在正常 3 着色,即 (Ir(W(m,n) 3. *2tn*x f故有 ( Ir(W(m,n)=3.f当 n 为奇数时,构造 Ir(W(m,n)的(3 n-1):(n-1)着色.对于集合1,2,3n-1, 当 j 为奇数时,顶点 uj1, uj2,
7、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 循环分配给 uj1, uj2,ujn.每个顶点分配 n-1 个元素; 当 j 为偶数时,顶点 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; t1,t2,tn 和中心顶点 x 均分配2 n+1,2n+2,3n-1; 中顶点分配*ji32n+1,2n
8、+2,3n-1; , , 和 中顶点可分配1,2,2n中的任意 n-1 个元素.由定*1t2*ntx义,这就是 Ir(W(m,n)的(3n-1):(n-1)着色.从而 f(Ir(W(m,n) .13另一方面,构造 Ir(W(m,n)的分数团 g,使得 = :对任意 y u11, ),(nIVyrgu12,u1n,有 g(y)= ;若 y=x,有 g(y)=1;若 y V(Ir(W(m,n)- x, u11, u12,u1n,有 g(y)=0.下12面证明对任意 Ir(W(m,n)中的极大独立集 S,有 1(所谓极大独立集 S 是指,对于任意y)y V(Ir(W(m,n)且 y S,有 S y不
9、是独立集). 由 g 的定义可知,要使 的值最大,独Sy)(立集中要尽可能多地包含最内圈中顶点或包含顶点 x.若 S 中包含 x, 则 S 不包含最内圈中任何顶点,从而有 =1;若 S 中存在最内圈中顶点,则 S 包含该圈的最大独立集但不包含 x.由Syg)(于长为 n 的奇圈的最大独立集基数为 ,从而有 =1.所以对任意 Ir(W(m,n)中的21nSyg)(极大独立集 S,有 1.从而对任意 Ir(W(m,n)中的独立集 S,有 1.根据定义,yg)(yg)g 是 Ir(W(m,n)的分数团.从而有 f(Ir(W(m,n) = .),(nIVyrg13综合上述两方面,当 n 为奇数时, f
10、(Ir(W(m,n)= .(2)设 中的顶点分别是 x1,x2, xr,相对应的各条悬挂边分别记为 e1,e2, ,er;边 xu11,xu12, *xxu1n 分别记为 e1, e2, en. 显然有 (S(Ir(W(m,n)= . 从而 incf (Ir(W(m,n) 2,34,45,3r或或 .下面证明 inc(Ir(W(m,n)= ,2,1rnnn或或. 2,34,45,3mr或或定义:图 G 的关联图 S(G)的某个正常着色具有性质 P,是指 : y V(G),设 NG(y)=y1,y2,yk,则(y 1,y1 y),( y2, y2 y),( yk, yk y)着相同的颜色.当 n
11、=3 时,首先用 6 种(因为 r 1,因此当 n=3 时,r+5 6)颜色着 S(W(m,3),并且在不考虑中心顶点 x 的情况下,使该着色具有性质 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)分
12、别着 5,6,4; ( u21, u11u21), ( u22, u12u22), 4( u23, u13u23)分别着 1,2,3.( u22, u21u22) , ( 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, ( u
13、23, u23u33)着 1; ( u31, u31u32), ( u33, u33u32)着 3; ( u31, u31u33), ( u32, u33u32)着 1;( u31, 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
14、)着 1, ( u61, u61u51), ( u52, u52u51), ( u53, u53u51)着 1; ( u42, u42u52), ( u51, u51u52), ( u53, 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,
15、u63u62), ( u72, u72u62)着 6; ( u53, u53u63), ( u61, u61u63) ,( u62, u62u63) ,( u73, u73u63)着 4.我们发现,第6 圈的着色和第 2 圈是一样的,因此第 7 圈的着色可与第 3 圈一样, ,以此构成循环,可以一直着下去.其次,将 S(W(m,3)的 6 着色推广到 S(Ir(W(m,3).对于 W(m,3)的中心顶点 x 而言,( x, e1),(x,e2),(x, er)分别着 5,7,8,r+5;而(x 1, e1),( x2,e2), (xr, er)可着 4 或 6;对于 uji,设在 S(W(m,
16、3)中包含在 W(m,3)中与 uji 关联的 4 条边的顶点的颜色集为 Uji，则 =5.设 中元素分别ji*ji为 , , ,则(u ji, uji ), (uji,uji ),(uji, uji )分别各着集合1,2,r+5-U ji 中的一1jiu2rji1ji2jirji种颜色,而( , uji ), ( ,uji ),( , uji )均着与在 S(W(m,3)中包含在 W(m,3)与 uji1jiji2jijirjirji相关联的边和相邻的顶点所组成的顶点一样的颜色. 例如 :对于点 u11,顶点( x,e1), ( u12, u11u12), ( u13, u13u11), (
17、 u21, u11u21)所着的颜色均为 1，则( , u11 ), ( ,u11 ),( , u11 )均121rr1着 1.用同样的方法可处理与 t1,t2,t3 相关的顶点的着色.从而 S(Ir(W(m,3)是 r+5 可着色的.当 n=4,m 2 时,S(W(m,4)可用 5 种颜色正常着色, 且使着色具有性质 P: (x,ei)着i(1 i 4); (u1i,ei)着 5 i(1 i 4);从而( u12, u12u11) ,(u14, u14u11) ,(u21, u11u21)着 1; (u13, u12u13) ,(u11, u12u11) ,(u22, u12u22)着 2;
18、(u12, u12u13), (u14, u14u13) ,(u23, u13u23)着 3;(u11, u14u11) ,(u13, u14u13), (u24, u14u24)着 4;因此(u 11, u21u11), (u22, u22u21) ,(u24, u24u21),(t1,t1u21)着 3; (u12, u22u12), (u21, u22u21) ,(u23, u23u22),(t2,t2u22)着 4;(u13, u23u13), (u22, u22u23) ,(u24, u24u23),(t3,t3u23)着 1; (u14, u24u14), (u21, u24u21
19、) ,(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 着色.当 n=4,r 2 m 3 时, n+r+1 7,下面给出 S(W(m,4)的满足性质 P 的正常 7 着色: (x,ei)着i(1 i 4); (u1i,ei)着 5 (1 i 4);从而(u 12, u12u11) ,(u14, u14u11) ,(u21, u11u21)着 1; (u13, u12u13) ,
20、(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;(u13, u23u13), (u22, u22u23) ,(u24, u24u23),(u33
21、, 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, u33u43)着 2; (u24, u24u34), (u31, u34u31) ,(u33,
22、 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),( u54, u54u44)着 4;(u41, u41u51), (u52, u5
23、2u51) ,(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, u64u61),( u71, u61u71)着 5; (u52, u62u
24、52), (u61, u62u61) ,(u63, u63u62),( u72, u62u72)着 4; (u53, u53u63), (u62, u62u63) ,(u64, u64u63),(u73, u63u73)着 2; (u54, 5u54u64), (u61, u64u61) ,(u63, u64u63),( u74, u74u64)着 6;(u61, u61u71),着 1; (u62, u62u72)着 7; (u63, u63u73)着 3; (u64, u64u74)着 4.由此,我们发现第 6 层相关顶点的着色和第 3 层完全一致,从而得到一个循环,第 7 层的相关着色和
25、第 4 层一致, 第 8 层的相关着色和第 5 层一致, .这就是 S(W(m,4)的满足性质 P 的正常 7 着色类似 n=3 的讨论,可知该 S(W(m,4)的 7 着色可推广到 S(Ir(W(m,4)的 r+5 着色.当 n 5 时,首先用 n+1 种颜色着 S(W(m,n),并使得着色具有性质 P.方法如下( 设该着色为 ): (x,ei)=i(1 i n); (u11,e1)= ( u12,e2)= (u1n,en)=n+1.从而 (u12, u11u12)= (u1n, u11u1n)= (u21, u11u21)=1; (u11, u11u12)= (u13, u12u13)=
26、(u22, u12u22)=2; ; (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)(2 j m); ( u(j+1)i, uji u(j+1)i)= ( uji, u(j-1)i uji)+2 (mod n)(2 j m); (uji, uji uj(i+1)= (u(j-1)i, u(j-1)i u(j-1)(i+1)+2 (mod n); (uji, uj
27、i uj(i-1)= (u(j-1)i, u(j-1)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 正常着色且具有性质 P.观察即知,对 W(m,n)中的顶点 u1i 来说,( x,xu1i),( u1(i+1), u1(i+1) u1i) ,( u1(i-1), u1(i-1) u1i) ,( u2i, u2iu1i)所着颜色相同.而对于 uji(2 j m)
28、来说,由于每一层的相关元素的色数为上一层加 2,因此和 uji 相邻的点和相关联的边构成的 S(W(m,n)中的顶点所着的颜色相同.所以只需说明是正常着色即可.直接观察可知,第一层着色是正常的.由于 着色是每一层对应元素加 2(mod n),因此只需验证第 2 层即可.对于 W(m,n)中的顶点 u2i,(u2i,u2(i+1)u2i)与 10 个顶点相邻,它们是( 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
29、) , (u2(i+1),u2(i+1) u2(i+2), (u2(i+1),u2(i+1) u1(i+1) ,( 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)与(u 2(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(
30、i+1) u3(i+1)着 i+5.从而这 10条边一共着 5 种颜色 i,i+1, i+2, i+4, i+5 (mod n).而(u 2i,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(当 j 3 时该值为 i-2), i-1,6 种颜色,而( u2i,u2iu1i)本身着颜色 i,所以( u2i,u2iu1i)不和相邻的边着相同的颜色(着相同颜色的两条
31、边的颜色差为 0 或 n 的整数倍,但 n 5). 与(u 2i,u3iu2i)相邻的 10 条边着 i,i+1, i+2,i+3,i+5,i+6,而(u2i,u3iu2i)本身着 i+4,所以(u 2i,u3iu2i)不和相邻的边着相同的颜色.因此与 W(m,n)中第二层顶点相关的 S(W(m,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 2,342,45,13r或或(Ir(W(m,n)= . ,3
32、2,45,13rnr或或(3) 显然有 (T(Ir(W(m,n)= .从而 (Ir(W(m,n) . 下,1rf4,135nr面证明 (Ir(W(m,n)= .4,35当 n=3 时,首先给出 T(W(m,3)的 5 着色 如下: (x)= ( u11u21)=1, (e1)= (u13)= ( u12u22)= (u21)=2, (e2)= ( u11)= ( u13u23)= (u22)=3, (e3)= (u23)=4, (u12)=5, 6(uj1uj2)=4 (1 j m), (uj2uj3)=1(1 j m), (uj3uj1)=5(1 j m), (uji)= ( u(j-1)i
33、 u(j-2)i) (1i 3, 3 j m), ( uji u(j-1)i)= (u(j-2)i) (1 i 3, 3 j m).最后, (ti)= (umiu(m-1)i); (tiumi)= (u(m-1)i). 从而由内到外,可得到 T(W(m,n)的 5 着色.其次, T(W(m,3)的 5 着色 可扩展到 T(Ir(W(m,3)的 r+5 着色:对于 W(m,3)中任意一点的 r 条悬挂边可分别着与该点和该点关联边不同的颜色,对于该点的 r 个悬挂点可着与该点在 W(m,3)中的某一条关联边相同的颜色.当 n 4 时,首先给出 T(W(m,n)的 n+1 着色 如下: (x)=n+
34、1; (ei)=i(1 i n); (u1i)=i+1(mod n)(1 i n); (ujiuj(i+1)=i-1 (mod n) (1 j m,1 i n); (u1iu2i)=n+1(1 i n); (u2i) =i (1 i n);继续扩展: (ujiu(j+1)i)= (u(j-1)i) (2 j m,1 i n); (uji)= (u(j-1)iu(j-2)i) (3 j m,1 i n); (ti)= (umiu(m-1)i); (tiumi)= (u(m-1)i).易证,可将 T(W(m,n)的 n+1 着色 扩展到 T(Ir(W(m,n)的 n+r+1 着色.从而 (Ir(W
35、(m,n) . 故 (Ir(W(m,n)= . (证毕)f4,135rf4,1353.一些推论根据以上得到的结论再结合分数色数与圆色数的关系,我们得到如下推论:推论 3.1 ( (m1,m2,mn)= ( (m1,m2,mn)=2; (S( (m1,m2,mn)=cnncn(S( (m1,m2,mn) = maxn+1, +3; (T( (m1,m2,mn)= c(T( (m1,m2,mn) = maxn+1, +3.nW推论 3.2 ( )= ( )=2 (n 为偶数); (S( )= (S( )=2m+1(m 2 或 m=1, n=3k);cCcmnCn(T( )= (T( )=2m+1(
36、m 2 或 m=1, n=3k).cmnn推论 3.3 (W(m,n)= (W(m,n)= 3(n 为偶数); (S(W(m,n)= (S(W(m,n)= c c; (T(W(m,n) = (T( W(m,n) = .5,143n或 c4,135推论 3.4 (Ir( (m1,m2,mn)= (Ir( (m1,m2,mn)=2; (S(Ir( (m1,m2,mn)= cnncn(S(Ir( (m1,m2,mn)= maxn+r+1, +r+3; (T(Ir( (m1,m2,mn)= Wc(T(Ir( (m1,m2,mn)= maxn+r+1, +r+3.n推论 3.5 (Ir( )= (Ir(
37、 )=2 (n 为偶数); (S(Ir( )= (S(Ir( )=2m+r+1 (m=1, cCcmnCnn=5, r=1 不同时成立); (T(Ir( )= (T(Ir( )=2m+r+1.cmn推论 3.6 (Ir(W(m,n)= (Ir(W(m,n)=3(n 为偶数); (S(Ir(W(m,n)= (S(Ir(W(m,n)= cc7; (T(Ir(W(m,n)= (T(Ir(W(m,n)= 不 同 时 成 立且 1,34,135rmnrn c.,注:推论中所述所有图形均为星极图.4.遗留问题本文主要研究了若干具有特殊结构图形的分数色数,从而为解决 MWIS 问题提供了理论依据.但根据以上
38、得到的结论,对于蛛网图及其 r-冠图,还有如下两个问题没有解决:（1）n=3,m 2 以及 n=4, m 3 时 W(m,n)的分数色数是多少？（2）n=4,r=1, m 3 时 Ir(W(m,n)的分数色数是多少？这两个问题有待进一步研究.参考文献:1 E.R.Scheinerman and D.H.Ullman. Fractional Graph TheoryM. John Wiley and Sons, Inc.New York,1997.2高炜,梁立,张超 . 超图的分数着色研究 J. 云南师范大学学报 (自然科学版). 2009, 29(1): 33-36.3高炜,梁立,夏幼明. 几
39、种特殊图形的分数色数研究J. 山西师范大学学报 (自然科学版). 2008,22(4):16-20.4刘玉记. 一类图的优美性J. 四川师范大学学报(自然科学版). 1995, 18(2):52-60.5卜长江,高振滨. 网图F (m , n 1, n2, , nm )的k-优美性J. 哈尔滨工程大学学报, 1995(1) : 102-106.6韦新,邓天炎,罗海鹏,黎贞崇. 几种特殊图的填充数J. 广西科学院学报. 2007 , 23 (4) : 217- 219.7 J.A.Bondy and U.S.R.Murty. Graph theory with applicationsM. Ne
40、w York: Macmillan Press Lid. 1976.8杨芳平,曹洪平,陈贵云. 4 p 2 阶群的非交换图及其对群结构的影响 J. 西南大学学报(自然科学版). 2009, 31(8):114-120.9李盛瑜,李霄民,雷澜. 关于积图的点连通度 J. 西南师范大学学报 (自然科学版). 2009, 34(5):22-24.10高炜,梁立,夏幼明. 一类整数距离图的分数色数 J. 西南师范大学学报( 自然科学版). 2009, 34(3):14-16.Fractional chromatic number of some graphs for the model of MWIS
41、 problemGAO Wei , LIANG Li， XIA You-ming（School of Computer Science and Information Technology, Yunnan Normal University, Kunming, 650092, China）Abstract: The issue of coloring is a very important in the graph theory. Fractional 8coloring as generalized coloring has used in many fields of computer s
42、cience, for example: MWIS problem. This paper gives formulas to compute the fractional chromatic number、 fractional incidence chromatic number and fractional total chromatic number of (m1,m2,mn)、 、W (m,n) and their r-corona graph.nCKey words: Fractional chromatic number; Fractional clique; Fractional incidence chromatic number; Fractional total chromatic number; star-extremal
