TY - JOUR
T1 - Large rainbow matchings in general graphs
AU - Aharoni, Ron
AU - Berger, Eli
AU - Chudnovsky, Maria
AU - Howard, David
AU - Seymour, Paul
N1 - Funding Information:
The research of the first author was supported by BSF, Israel Grant No. 2006099, by ISF, Israel Grant No. 2023464, by the Technion's research promotion fund, Israel, and by the Discont Bank chair, Israel..The research of the second author was supported by BSF Grant No. 2006099 and by ISF Grant No. 2023464.The research of the third author was supported by BSF Grant No. 2006099, and NSF grants DMS-1001091 and IIS-1117631..The research of the fourth author was supported by BSF Grant No. 2006099, and by ISF Grant Nos. 779/08, 859/08 and 938/06..The research of the fifth author was supported by ONR grant N00014-14-1-0084 and NSF grant DMS-1265563.. We are grateful to Danny Kotlar and Tung Nguyen for useful remarks.
Publisher Copyright:
© 2019 Elsevier Ltd
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 -