Representation of large matchings in bipartite graphs

DOI10.1137/16M1062958zbMATH Open1368.05116arXiv1601.00943MaRDI QIDQ5348494FDOQ5348494

Authors: Ron Aharoni, Dani Kotlar, Ran Ziv 

Publication date: 18 August 2017

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

Abstract: Let $f(n)$ be the smallest number such that every collection of $n$ matchings, each of size at least $f(n)$, in a bipartite graph, has a full rainbow matching. Generalizing famous conjectures of Ryser, Brualdi and Stein, Aharoni and Berger conjectured that $f(n)=n+1$ for every $n>1$. Clemens and Ehrenm{"u}ller proved that $f(n)lefrac32n+o(n)$. We show that the $o(n)$ term can be reduced to a constant, namely $f(n)lelceilfrac32nceil+1$.

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

Recommendations

• Large matchings in bipartite graphs have a rainbow matching
• Large rainbow matchings in general graphs
• Rainbow matchings in bipartite multigraphs
• On rainbow matchings in bipartite graphs
• Rainbow matchings in \(r\)-partite \(r\)-graphs

zbMATH Keywords

transversalrainbow matchingbipatite graph

Mathematics Subject Classification ID

Distance in graphs (05C12) 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
• Transversals in Latin squares: a survey
• Large matchings in bipartite graphs have a rainbow matching
• An improved bound on the sizes of matchings guaranteeing a rainbow matching
• On a generalization of the Ryser-Brualdi-Stein conjecture
• Rainbow matchings and connectedness of coloured graphs
• On sets not belonging to algebras and rainbow matchings in graphs

Cited In (11)

• From one to many rainbow Hamiltonian cycles
• Title not available (Why is that?)
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Fair representation in the intersection of two matroids
• An inductive characterization of matching in binding bigraphs
• Full rainbow matchings in graphs and hypergraphs
• Large matchings in bipartite graphs have a rainbow matching
• Rainbow paths and large rainbow matchings
• Rainbow matchings and rainbow connectedness
• An approximate version of a conjecture of Aharoni and Berger
• Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets

This page was built for publication: Representation of large matchings in bipartite graphs

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