pith. sign in

arxiv: 1204.3193 · v1 · pith:B7QVFNBBnew · submitted 2012-04-14 · 🧮 math.CO

Large rainbow matchings in large graphs

classification 🧮 math.CO
keywords largerainbowcolorcolorsdegreeedgesgraphleast
0
0 comments X
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.