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.