Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653679 | European Journal of Combinatorics | 2014 | 5 Pages |
Abstract
Let g(n)g(n) be the least number such that every collection of nn matchings, each of size at least g(n)g(n), in a bipartite graph, has a full rainbow matching. Aharoni and Berger (2009) conjectured that g(n)=n+1g(n)=n+1 for every n>1n>1. This generalizes famous conjectures of Ryser, Brualdi and Stein. Recently, Aharoni et al. proved that g(n)≤⌊74n⌋. We prove that g(n)≤⌊53n⌋.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Daniel Kotlar, Ran Ziv,