Large rainbow matchings in large graphs

MaRDI QIDQ6232331zbMATH OpenFDO

Authors Alexandr Kostochka, Florian Pfender, Matthew Yancey

Publication date 14 April 2012

Abstract: A extit{rainbow subgraph} of an edge-colored graph is a subgraph whose edges have distinct colors. The extit{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, $ngeq4.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 page was built for publication: Large rainbow matchings in large graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6232331)