Large rainbow matchings in general graphs. (June 2019)

• Record Type: Journal Article
• Authors: Aharoni, Ron; Berger, Eli; Chudnovsky, Maria; Howard, David; Seymour, Paul
• Is Part Of: European journal of combinatorics. Volume 79(2019)
• Page Start: 222
• Page End: 227
• Publication Date: 2019-06
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2019.01.012
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: By a theorem of Drisko, any 2 n − 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 2 n matchings of size n suffice. We prove that any 3 n − 2 matchings of size n have a rainbow matching of size n .