Large rainbow matchings in large graphs

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\ge 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$.

Cited by in corpus (1)

• A note on large rainbow matchings in edge-coloured graphs