Quantcast

Large rainbow matchings in general graphs

Research paper by Ron Aharoni, Eli Berger, Maria Chudnovsky, David Howard, Paul Seymour

Indexed on: 11 Nov '16Published on: 11 Nov '16Published in: arXiv - Mathematics - Combinatorics



Abstract

By a theorem of Drisko, any $2n-1$ matchings of size $n$ in a bipartite graph have a partial rainbow matching of size $n$. Bar\'at, Gy\'arf\'as and S\'ark\"ozy conjectured that if $n$ is odd then the same is true also in general graphs, and that if $n$ is even then $2n$ matchings of size $n$ suffice. We prove that any $3n-2$ matchings of size $n$ have a partial rainbow matching of size $n$.