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

Jennifer Diemunsch, Michael Ferrara, Allan Lo, Casey Moffatt, Florian Pfender, Paul S Wenger

Abstract


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

Keywords


Rainbow matching; Properly edge-colored graphs

Full Text: PDF