Large rainbow matchings in general graphs

Ron Aharoni, Eli Berger, Maria Chudnovsky, David Howard, Paul Seymour

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)222-227
Number of pages6
JournalEuropean Journal of Combinatorics
Volume79
DOIs
StatePublished - Jun 2019

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Large rainbow matchings in general graphs'. Together they form a unique fingerprint.

  • Cite this