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