Excessive factorizations of bipartite multigraphs.

An excessive factorization of a multigraph G is a set F = {F(1), F(2), ... F(r)) 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 chi'(e)(G). We set chi'(e)(G) = infinity if an excessive factorization does not exist. Analogously, let m be a fixed positive integer. An excessive vertical bar m vertical bar-factorization is a set M = {M(1), M(2) ... M(k)} 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 chi'([m])(G) and called the excessive [m]-index of G. Again, we set chi'(vertical bar m vertical bar) (G) = infinity if an excessive [m]-factorization does not exist. In this paper we shall prove that, for bipartite multigraphs, both the parameters chi'(e) and chi'([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.