Large rainbow matchings in general graphs
classification
🧮 math.CO
keywords
sizematchingsrainbowgeneralgraphsmatchingpartialthen
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.