Excessive factorizations of bipartite multigraphs

An excessive factorization of a multigraph G is a set F=F1,F2,⋯,Fr of 1-factors of G whose union is E(G) and, subject to this condition, r is minimum. The integer r is called the excessive index of G and denoted by χe′(G). We set χe′(G)=∞ if an excessive factorization does not exist. Analogously, let m be a fixed positive integer. An excessive [m]-factorization is a set M=M1,M2,⋯,Mk of matchings of G, all of size m, whose union is E(G) and, subject to this condition, k is minimum. The integer k is denoted by χ[m]′(G) and called the excessive [m]-index of G. Again, we set χ[m]′(G)=∞ if an excessive [m]-factorization does not exist. In this paper we shall prove that, for bipartite multigraphs, both the parameters χe′ and χ[m]′ are computable in polynomial time, and we shall obtain an efficient algorithm for finding an excessive factorization and excessive [m]-factorization, respectively, of any bipartite multigraph.