Rainbow matching in edge-colored graphs
type: Item
instance of: scholarly article
title: Rainbow matching in edge-colored graphs
zbMATH Open document ID: 1188.05063
author: Timothy D. Lesaulnier
author: Christopher J. Stocker
author: Paul S. Wenger
author: Douglas B. West
published in: The Electronic Journal of Combinatorics
publication date: 2010-06-16T00:00:00Z
full work available at URL: https://eudml.org/doc/222586
full work available at URL: v17i1n26.html
review text: Summary: A rainbow subgraph of an edge-colored graph is a subgraph whose edges have distinct colors. The color degree of a vertex \(v\) is the number of different colors on edges incident to \(v\). \textit{G. Wang} and \textit{H. Li} [``Heterochromatic matchings in edge-colored graphs'', Electron. J. Comb. 15, No.\,1, Research Paper R138 (2008; Zbl 1165.05330)] conjectured that for \(k \geqslant 4\), every edge-colored graph with minimum color degree at least \(k\) contains a rainbow matching of size at least \(\lceil k/2\rceil \). We prove the slightly weaker statement that a rainbow matching of size at least \(\lfloor k/2\rfloor\) is guaranteed. We also give sufficient conditions for a rainbow matching of size at least \(\lceil k/2\rceil\) that fail to hold only for finitely many exceptions (for each odd \(k\)).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 5721435
zbMATH Keywords: rainbow subgraph
zbMATH Keywords: color degree
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5721435