On the Complexity of Computing the Excessive [B]-Index of a Graph

Let B be a positive integer and let G be a simple graph. An excessive [B]-factorization of G is a minimum set of matchings, each of size B, whose union is E(G). The number of matchings in an excessive [B]-factorization of G (or ∞ if an excessive [B]-factorization does not exist) is a graph parameter called the excessive [B]-index of G and denoted by χ[B]′(G). In this article we prove that, for any fixed value of B, the parameter χ[B]′(G) can be computed in polynomial time in the size of the graph G. This solves a problem posed by one of the authors at the 21st British Combinatorial Conference. © 2015 Wiley Periodicals, Inc.