Rainbow matchings of size δ(G) in properly edge-colored graphs
Research output: Contribution to journal › Article › peer-review
Authors
Colleges, School and Institutes
External organisations
- University of Colorado-Denver
- Universität Rostock
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(δ) such that a properly edge-colored graph G with minimum degree δ and order at least f(δ) must have a rainbow matching of size δ. We answer this question in the affirmative; an extremal approach yields that f(δ) = 98δ/23 < 4.27δ suffices. Furthermore, we give an O(δ(G)\V(G)\ 2)-time algorithm that generates such a matching in a properly edge-colored graph of order at least 6.5δ.
Details
Original language | English |
---|---|
Journal | Electronic Journal of Combinatorics |
Volume | 19 |
Issue number | 2 |
Publication status | Published - 28 Jun 2012 |
Keywords
- Properly edge-colored graphs, Rainbow matching