Rainbow matchings in properly colored multigraphs

DOI10.1137/17M1151742zbMATH Open1391.05209arXiv1710.03041OpenAlexW2962982788WikidataQ129529344 ScholiaQ129529344MaRDI QIDQ3174698FDOQ3174698

Authors: Peter Keevash, L. Yepremyan 

Publication date: 18 July 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Aharoni and Berger conjectured that in any bipartite multigraph that is properly edge-coloured by $n$ colours with at least $n+1$ edges of each colour there must be a matching that uses each colour exactly once. In this paper we consider the same question without the bipartiteness assumption. We show that in any multigraph with edge multiplicities $o(n)$ that is properly edge-coloured by $n$ colours with at least $n+o(n)$ edges of each colour there must be a matching of size $n-O(1)$ that uses each colour at most once.

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

Recommendations

• An approximate version of a conjecture of Aharoni and Berger
• Rainbow matchings in bipartite multigraphs
• Full rainbow matchings in graphs and hypergraphs
• Rainbow matchings in properly colored bipartite graphs
• Rainbow matchings and rainbow connectedness

zbMATH Keywords

Latin squaresmatchings

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15)

Cites Work

• Transversals of latin squares and their generalizations
• Rainbow matchings in \(r\)-partite \(r\)-graphs
• Combinatorial matrix theory
• A lower bound for the length of a partial transversal in a Latin square
• Transversals in Latin squares: a survey
• An approximate version of a conjecture of Aharoni and Berger

Cited In (23)

• Rainbow matchings in properly-colored hypergraphs
• How many colors guarantee a rainbow matching?
• An improved bound on the sizes of matchings guaranteeing a rainbow matching
• Rainbow matchings in properly colored bipartite graphs
• Title not available (Why is that?)
• Repeated patterns in proper colorings
• A rainbow \(k\)-matching in the complete graph with \(r\) colors
• Choice functions
• Full rainbow matchings in graphs and hypergraphs
• Rainbow matchings and connectedness of coloured graphs
• Short Proofs of Rainbow Matchings Results
• A rainbow blow-up lemma
• Existence of rainbow matchings in properly edge-colored graphs
• Graph theory. Abstracts from the workshop held January 6--12, 2019
• Rainbow matchings of size \(m\) in graphs with total color degree at least \(2mn\)
• Rainbow matchings and transversals
• Cooperative conditions for the existence of rainbow matchings
• On Rainbow Matchings for Hypergraphs
• Topological methods for the existence of a rainbow matching
• Rainbow matchings and rainbow connectedness
• Rainbow perfect matchings in \(r\)-partite graph structures
• Rainbow matchings in bipartite multigraphs
• An approximate version of a conjecture of Aharoni and Berger

This page was built for publication: Rainbow matchings in properly colored multigraphs

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