Can I read Rainbow Paths and Large Rainbow Matchings on EtoBox?

Rainbow Paths and Large Rainbow Matchings by Aharoni, Ron; Berger, Eli; Chudnovsky, Maria; Zerbib, Shira is a scholarly article available to read on EtoBox.

What is Rainbow Paths and Large Rainbow Matchings about?

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 of $\frac{2}{3}n-1$, improving on the trivial $\frac{1}{2}n$, and an analogous result for hypergraphs. For $\{C_3,C_5\}$-free graphs and for disjoint matchings we obtain a lower bound of $\frac{3n}{4}-O(1)$. We also discuss a conjecture on rainbow alternating paths, that if true would yield a lower bound of $n-\sqrt{2n}$. We prove the non-alternating (ordinary paths) version of this conjecture.

Author

Aharoni, Ron; Berger, Eli; Chudnovsky, Maria; Zerbib, Shira

Published

2020

Language

EN