Rainbow matchings of size \(\delta(G)\) in properly edge-colored graphs
type: Item
instance of: scholarly article
title: Rainbow matchings of size \(\delta(G)\) in properly edge-colored graphs
zbMATH Open document ID: 1253.05113
author: Jennifer Diemunsch
author: Michael Ferrara
author: Allan Lo
author: Casey Moffatt
author: Florian Pfender
author: Paul S. Wenger
published in: The Electronic Journal of Combinatorics
publication date: 2012-10-24T00:00:00Z
full work available at URL: https://arxiv.org/abs/1108.2521
full work available at URL: v19i2p52
review text: 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\).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 6098339
zbMATH Keywords: rainbow matching
zbMATH Keywords: properly edge-colored graphs
MaRDI profile type: Publication
arXiv ID: 1108.2521
description: scientific article; zbMATH DE number 6098339