Abstract
Drisko \cite{drisko} proved (essentially) that every family of matchings of size in a bipartite graph possesses a partial rainbow matching of size . In \cite{bgs} this was generalized as follows: Any matchings of size in a bipartite graph have a rainbow matching of size . We extend this latter result to matchings of not necessarily equal cardinalities. Settling a conjecture of Drisko, we characterize those families of matchings of size in a bipartite graph that do not possess a rainbow matching of size . Combining this with an idea of Alon \cite{alon}, we re-prove a characterization of the extreme case in a well-known theorem of Erdős-Ginzburg-Ziv in additive number theory.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.