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

zbMATH Open1253.05113arXiv1108.2521MaRDI QIDQ456311FDOQ456311

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

Publication date: 24 October 2012

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: A {it 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; f(delta) = 6.5delta suffices. Furthermore, the proof provides a O(delta(G)|V(G)|^2)-time algorithm that generates such a matching.

Full work available at URL: https://arxiv.org/abs/1108.2521

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Rainbow matchings in properly edge colored graphs
• Existence of rainbow matchings in properly edge-colored graphs
• Rainbow matchings in strongly edge-colored graphs
• Rainbow matching in edge-colored graphs
• Large rainbow matchings in edge-coloured graphs

zbMATH Keywords

rainbow matchingproperly edge-colored graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (16)

• Large rainbow matchings in edge-colored graphs with given average color degree
• Longest partial transversals in plexes
• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• Large rainbow matchings in semi-strong edge-colorings of graphs
• Existence of rainbow matchings in strongly edge-colored graphs
• Orthogonal matchings revisited
• A rainbow \(k\)-matching in the complete graph with \(r\) colors
• Complexity results for rainbow matchings
• Rainbow matchings in properly edge colored graphs
• A note on large rainbow matchings in edge-coloured graphs
• A note on rainbow matchings in strongly edge-colored graphs
• Existence of rainbow matchings in properly edge-colored graphs
• Rainbow matchings of size \(m\) in graphs with total color degree at least \(2mn\)
• Existences of rainbow matchings and rainbow matching covers
• Rainbow matchings and cycle-free partial transversals of Latin squares
• Quadratic vertex kernel for rainbow matching

This page was built for publication: Rainbow matchings of size \(\delta(G)\) in properly edge-colored graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456311)