## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 1760-1766 |

Number of pages | 7 |

Journal | Discrete Applied Mathematics |

Volume | 158 |

Issue number | 16 |

DOIs | |

Publication status | Published - 28 Aug 2010 |

## Keywords

- Bipartite multigraph
- Excessive factorization
- Matching theory
- Network flow
- Vertex cover