Efficient algorithms for the edge-cover coloring problem
Qin Chen · Scientia Sinica Mathematica · 2016
Let G=(V,E) be a multigraph. An edge subset F of E is called an edge cover if the sub-graph 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.