边覆盖染色问题的有效算法  

Efficient algorithms for the edge-cover coloring problem

作　　者：陈琴[1] 

机构地区：[1]中国计量学院理学院,杭州310018

出　　处：《中国科学：数学》2016年第3期351-370,共20页Scientia Sinica：Mathematica

摘　　要：设G=(V,E)是一个重图.若边子集F的导出子图是G的一个生成子图,则称F为G的一个边覆盖.G的边覆盖色数ξ(G)是使得G可划分的最大不交边覆盖数.用δ(G)表示G的最小阶,令ρ(G)=min{2|?(U)|/(|U|+1):U?V(G),|U|≥3为奇数},其中?(U)表示至少有一个端点在U中的边集合.显然,ξ(G)≤min{δ(G),「ρ(G)」}.本文证明了,对系列平行重图和近似二部重图,此处等号成立,并且通过证明得到计算这两类重图的边覆盖色数的多项式时间算法.Let G =（V, E） be a multigraph. An edge subset F of E is called an edge cover if the subgraph induced by F is a spanning subgraph of G. The cover index, denoted by ξ（G）, is the maximum number of disjoint edge covers in G. Let δ（G） be the minimum valency of G and let ρ（G） = min{2｜？（U）｜/（｜U｜＋1）：U？V（G）,｜U｜≥3, and ｜U｜ is odd}, where ？（U） consists of all edges with at least one end in U. Evidently,ξ（G） min{δ（G）, 「ρ（G）」}. In this paper, we show that equality holds for series-parallel multigraphs and nearly bipartite multigraphs; our proof also yields a polynomial-time algorithm for computing the cover index of such multigraphs.

关 键 词：边覆盖染色 系列平行重图 近似二部重图 

分 类 号：O157.5[理学—数学]