Article ID Journal Published Year Pages File Type
5777343 European Journal of Combinatorics 2018 8 Pages PDF
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
, , ,