Rainbow matchings of size δ(G) in properly edge-colored graphs

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)

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

Original languageEnglish
JournalElectronic Journal of Combinatorics
Volume19
Issue number2
Publication statusPublished - 28 Jun 2012

Keywords

  • Properly edge-colored graphs
  • Rainbow matching

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Rainbow matchings of size δ(G) in properly edge-colored graphs'. Together they form a unique fingerprint.

Cite this