Rainbow Matchings of Size $\delta(G)$ in Properly Edge-Colored Graphs

  • Jennifer Diemunsch
  • Michael Ferrara
  • Allan Lo
  • Casey Moffatt
  • Florian Pfender
  • Paul S Wenger
Keywords: Rainbow matching, Properly edge-colored graphs


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$. 
Article Number