几种特殊图形的分数色数研究 - 西南大学.doc

MWIS问题模型中几类图形的分数色数 高炜 梁立* 夏幼明 (云南师范大学计算机科学与信息技术学院,云南 昆明 650092) 摘要：图的着色问题是图论的重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用,例如MWIS问题.给出了齿顶边星图、、蛛网图以及它们的r-冠图的分数色数、分数关联色数和分数全色数. 关键词：分数色数；分数团；分数关联色数; 分数全色数; 星极图 中图分类号: TQ92 文献标识码： A 1 基本概念和引理 与图的分数着色有关的研究最早可以追溯到1970年对图的多重着色的研究. E.R.Scheinerman和D.H.Ullman在[1]中有关于此专题的较为详尽的论述. 图的分数色数有着十分广泛的应用, 例如MWIS问题. 处理这个问题的模型是无向图G = (V, E) . 图中每个顶点表示一台处理器,顶点与顶点之间存在边当且仅当顶点所代表的处理器之间有共享的资源. MWIS问题等价于分数着色问题.研究特殊图形的分数色数有助于解决特殊多处理器结构下的MWIS问题,相关内容可参考[2,3]. 关于齿顶边星图(m1,m2,…,mn),,蛛网图W(m,n) 的定义可参考[4,5,6]. 在G的r-冠图中,顶点v上粘接的r条悬挂边的端点集记作v*. (本文只考虑无向、简单、有限图.文中涉及的符号和标记若没有特别说明,则与[7]一致) 2.主要定理以及证明 本文给出了齿顶边星图、、蛛网图以及它们的r-冠图的几种分数色数如下： 定理2.1 f ((m1,m2,…,mn))=2; incf ((m1,m2,…,mn))=max{n+1, +3}; ((m1,m2,…,mn))= max{n+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)))=max{n+r+1,+r+3}; (Ir((m1,m2,…,mn)))=max{n+r+1, +r+3}. 定理2.5f (Ir())=; incf (Ir())= ;(Ir())=2m+r+1. 定理2.6f (Ir(W(m,n)))=; incf (Ir(W(m,n)))= ; (Ir(W(m,n)))= . 由于篇幅有限,这里只给出定理2.6的详细证明过程,用类似的方法可证明其他结论. 定理2.6证明: (1)当n为偶数时,一方面Ir(W(m,n))中存在K3,由f (K3 )=3知(Ir(W(m,n)))3.另一方面,在W(m,n)中记从内到外第j(1jm)个圈相对应的n个顶点为 uj1,uj2,…,ujn; 相对应的n个外部悬挂点为 t1,t2,…,tn; 中心顶点为x. 对于uji (1jm, 1in),若i+j=奇数,则着颜色1.若i+j=偶数,则着颜色2; t1,t2,…,tn和中心顶点x着颜色3. 中顶点均着颜色3; , ,…, 和中顶点均着颜色1或2.从而Ir(W(m,n))存在正常3着色,即(Ir(W(m,n)))3. 故有( Ir(W(m,n)))=3. 当n为奇数时,构造Ir(W(m,n))的(3n-1):(n-1)着色.对于集合{1,2,…,3n-1},当j为奇数时,顶点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}循环分配给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均分配{2n+1,2n+2,…,3n-1}; 中顶点分配{2n+1,2n+2,…,3n-1}; , ,…, 和中顶点可分配{1,2,…,2n}中的任意n-1个元素.由定义,这就是Ir(W(m,n))的(3n-1):(n-1)着色.从而f(Ir(W(m,n))). 另一方面,构造Ir(W(m,n))的分数团g,使得=:对任意y{u11, u12,…,u1n},有g(y)=;若y=x,有g(y)=1;若yV(Ir(W(m,n