Article ID Journal Published Year Pages File Type
4653679 European Journal of Combinatorics 2014 5 Pages PDF
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
, ,