Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777343 | European Journal of Combinatorics | 2018 | 8 Pages |
Abstract
Drisko (1998) proved (essentially) that every family of 2nâ1 matchings of size n in a bipartite graph possesses a partial rainbow matching of size n. In Barát et al. (2017) this was generalized as follows: Any âk+2k+1nââ(k+1) matchings of size n in a bipartite graph have a rainbow matching of size nâk. The paper has a twofold aim: (i) to extend these results to matchings of not necessarily equal cardinalities, and (ii) to prove a conjecture of Drisko, on the characterization of those families of 2nâ2 matchings of size n in a bipartite graph that do not possess a rainbow matching of size n. Combining the latter with an idea of Alon (2011), we re-prove a characterization of the extreme case in a well-known theorem of ErdÅs-Ginzburg-Ziv in additive number theory.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ron Aharoni, Dani Kotlar, Ran Ziv,