A note on large rainbow matchings in edge-coloured graphs

Abstract

A rainbow subgraph in an edge-coloured graph is a subgraph such that its edges have distinct colours. The minimum colour degree of a graph is the smallest number of distinct colours on the edges incident with a vertex over all vertices. Kostochka, Pfender, and Yancey showed that every edge-coloured graph on $n$ vertices with minimum colour degree at least $k$ contains a rainbow matching of size at least $k$, provided $n\ge (17/4)k^2$. In this paper, we show that $n\ge 4k-4$ is sufficient for $k\ge 4$.

References in corpus (1)

• Large rainbow matchings in large graphs