On the Complexity of Computing the Excessive [B]‐Index of a Graph
David Cariolaro, Roméo Rizzi · Journal of Graph Theory · 2015
Abstract 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 . 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 . In this article we prove that, for any fixed value of B, the parameter 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.