Rainbow matchings of size \(\delta(G)\) in properly edge-colored graphs (Q456311)

Summary: A rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors. Wang asked if there is a function \(f(\delta)\) such that a properly edge-colored graph \(G\) with minimum degree \(\delta\) and order at least \(f(\delta)\) must have a rainbow matching of size \(\delta\). We answer this question in the affirmative; an extremal approach yields that \(f(\delta) = 98\delta/23< 4.27\delta\) suffices. Furthermore, we give an \(O(\delta(G)|V(G)|^2)\)-time algorithm that generates such a matching in a properly edge-colored graph of order at least \(6.5\delta\).