Options
An improved bound on the sizes of matchings guaranteeing a rainbow matching
Publikationstyp
Journal Article
Date Issued
2016-04-15
Sprache
English
Author(s)
Institut
TORE-URI
Journal
Volume
23
Issue
2
Article Number
P2.11
Citation
Electronic Journal of Combinatorics 2 (23): P2.11 (2016-04-15)
A conjecture by Aharoni and Berger states that every family of n matchings of size n + 1 in a bipartite multigraph contains a rainbow matching of size n. In this paper we prove that matching sizes of (3/2 + o(1))n suffice to guarantee such a rainbow matching, which is asymptotically the same bound as the best-known one in the case where we only aim to find a rainbow matching of size n – 1. This improves previous results by Aharoni, Charbit and Howard, and Kotlar and Ziv.
Subjects
Bipartite graphs
Rainbow matchings