Rainbow paths and large rainbow matchings (Q2073301): Difference between revisions

Summary: 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.