Excessive factorizations of bipartite multigraphs

An excessive factorization   of a multigraph GG is a set F={F1,F2,…,Fr}F={F1,F2,…,Fr} of 1-factors of GG whose union is E(G)E(G) and, subject to this condition, rr is minimum. The integer rr is called the excessive index   of GG and denoted by χe′(G). We set χe′(G)=∞ if an excessive factorization does not exist. Analogously, let mm be a fixed positive integer. An excessive  [m][m]-factorization   is a set M={M1,M2,…,Mk}M={M1,M2,…,Mk} of matchings of GG, all of size mm, whose union is E(G)E(G) and, subject to this condition, kk is minimum. The integer kk is denoted by χ[m]′(G) and called the excessive   [m][m]-index   of GG. Again, we set χ[m]′(G)=∞ if an excessive [m][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][m]-factorization, respectively, of any bipartite multigraph.