Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423637 | Electronic Notes in Discrete Mathematics | 2016 | 6 Pages |
Abstract
We present recent results regarding rainbow matchings in bipartite graphs. Using topological methods we address a known conjecture of Stein and show that if Kn,n is partitioned into n sets of size n, then a partial rainbow matching of size 2n/3 exists. We generalize a result of Cameron and Wanless and show that for any n matchings of size n in a bipartite graph with 2n vertices there exists a full matching intersecting each matching at most twice. We show that any n matchings of size approximately 3n/2 have a rainbow matching of size n. Finally, we show the uniqueness of the extreme case for a theorem of Drisko and provide a generalization of Drisko's theorem.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ron Aharoni, Eli Berger, Dani Kotlar, Ran Ziv,