Rainbow paths and large rainbow matchings

Ron Aharoni, Eli Berger, Maria Chudnovsky, Shira Zerbib

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

A conjecture of the first two authors is that n matchings of size n in any graph have a rainbow matching of size n−1. We prove a lower bound of23n−1, improving on the trivial12n, and an analogous result for hypergraphs. For{C3, C5}-free graphs and for disjoint matchings we obtain a lower bound of3n4 − O(1). We also discuss a conjecture on rainbow alternating paths, that if true would yield a lower bound of n −√2n. We prove the non-alternating (ordinary paths) version of this conjecture.

Original languageEnglish (US)
Article numberP1.10
JournalElectronic Journal of Combinatorics
Volume29
Issue number1
DOIs
StatePublished - 2022

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Rainbow paths and large rainbow matchings'. Together they form a unique fingerprint.

Cite this