Rainbow matchings in properly colored multigraphs

DOI10.1137/17M1151742MaRDI QIDQ3174698zbMATH OpenOpenAlexWikidataFDO

Authors Peter Keevash, L. Yepremyan

Publication date 18 July 2018

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

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

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)

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.

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

Cites work

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

Cited in

(23)

• Rainbow matchings in bipartite multigraphs
• Existence of rainbow matchings in properly edge-colored graphs
• Short Proofs of Rainbow Matchings Results
• An improved bound on the sizes of matchings guaranteeing a rainbow matching
• A rainbow \(k\)-matching in the complete graph with \(r\) colors
• 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\)
• How many colors guarantee a rainbow matching?
• Full rainbow matchings in graphs and hypergraphs
• A rainbow blow-up lemma
• Rainbow matchings and transversals
• Repeated patterns in proper colorings
• Topological methods for the existence of a rainbow matching
• Choice functions
• Cooperative conditions for the existence of rainbow matchings
• An approximate version of a conjecture of Aharoni and Berger
• Rainbow matchings in properly colored bipartite graphs
• Rainbow matchings in properly-colored hypergraphs
• Rainbow matchings and connectedness of coloured graphs
• Rainbow matchings and rainbow connectedness
• Rainbow perfect matchings in \(r\)-partite graph structures
• scientific article; zbMATH DE number 4079450 (Why is no real title available?)
• On Rainbow Matchings for Hypergraphs

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)