TY - JOUR
T1 - Large rainbow matchings in general graphs
AU - Aharoni, Ron
AU - Berger, Eli
AU - Chudnovsky, Maria
AU - Howard, David
AU - Seymour, Paul
PY - 2019/6
Y1 - 2019/6
N2 - By a theorem of Drisko, any 2n−1 matchings of size n in a bipartite graph have a rainbow matching of size n. Inspired by results and discussion of Barát, Gyárfás and Sárközy, we conjecture 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 rainbow matching of size n.
AB - By a theorem of Drisko, any 2n−1 matchings of size n in a bipartite graph have a rainbow matching of size n. Inspired by results and discussion of Barát, Gyárfás and Sárközy, we conjecture 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 rainbow matching of size n.
UR - http://www.scopus.com/inward/record.url?scp=85063630593&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85063630593&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2019.01.012
DO - 10.1016/j.ejc.2019.01.012
M3 - Article
AN - SCOPUS:85063630593
VL - 79
SP - 222
EP - 227
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
SN - 0195-6698
ER -