Large rainbow matchings in large graphs
classification
🧮 math.CO
keywords
largerainbowcolorcolorsdegreeedgesgraphleast
read the original abstract
A \textit{rainbow subgraph} of an edge-colored graph is a subgraph whose edges have distinct colors. The \textit{color degree} of a vertex $v$ is the number of different colors on edges incident to $v$. We show that if $n$ is large enough (namely, $n\geq 4.25k^2$), then each $n$-vertex graph $G$ with minimum color degree at least $k$ contains a rainbow matching of size at least $k$.
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.