Representation of large matchings in bipartite graphs

DOI10.1137/16M1062958MaRDI QIDQ5348494zbMATH OpenFDO

Authors Ron Aharoni, Dani Kotlar, Ran Ziv

Publication date 18 August 2017

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

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

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)

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$.

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

Cites work

• An improved bound on the sizes of matchings guaranteeing a rainbow matching
• Combinatorial matrix theory
• Large matchings in bipartite graphs have a rainbow matching
• On a generalization of the Ryser-Brualdi-Stein conjecture
• On sets not belonging to algebras and rainbow matchings in graphs
• Rainbow matchings and connectedness of coloured graphs
• Rainbow matchings in r-partite r-graphs
• Transversals in Latin squares: a survey
• Transversals of latin squares and their generalizations

Cited in

(11)

• Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets
• From one to many rainbow Hamiltonian cycles
• scientific article; zbMATH DE number 5909229 (Why is no real title available?)
• 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

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)