pith. sign in

arxiv: 1611.03648 · v5 · pith:JRWGR7MGnew · submitted 2016-11-11 · 🧮 math.CO

Large rainbow matchings in general graphs

classification 🧮 math.CO
keywords sizematchingsrainbowgeneralgraphsmatchingpartialthen
0
0 comments X
read the original abstract

By a theorem of Drisko, any $2n-1$ matchings of size $n$ in a bipartite graph have a partial rainbow matching of size $n$. Inspired by discussion of Bar\'at, Gy\'arf\'as and S\'ark\"ozy, 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 partial rainbow matching of size $n$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.