Rainbow Matchings of Size $\delta(G)$ in 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$....

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2012-06, Vol.19 (2)
Main Authors: Diemunsch, Jennifer, Ferrara, Michael, Lo, Allan, Moffatt, Casey, Pfender, Florian, Wenger, Paul S
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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$. 
ISSN:1077-8926
1077-8926
DOI:10.37236/2443