Large rainbow matchings in general graphs

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

doi:10.1016/j.ejc.2019.01.012

Large rainbow matchings in general graphs

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

Mathematics

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	222-227
Number of pages	6
Journal	European Journal of Combinatorics
Volume	79
DOIs	https://doi.org/10.1016/j.ejc.2019.01.012
State	Published - Jun 2019

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2019.01.012

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

Cite this

@article{75adcfb153e24fc99dbfba68bfe51706,

title = "Large rainbow matchings in general graphs",

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{\'a}t, Gy{\'a}rf{\'a}s and S{\'a}rk{\"o}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.",

author = "Ron Aharoni and Eli Berger and Maria Chudnovsky and David Howard and Paul Seymour",

year = "2019",

month = jun,

doi = "10.1016/j.ejc.2019.01.012",

language = "English (US)",

volume = "79",

pages = "222--227",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press Inc.",

}

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 -