An improved bound on the sizes of matchings guaranteeing a rainbow matching

MaRDI QIDQ281599zbMATH OpenFDO

Authors Dennis Clemens, Julia Ehrenmüller

Publication date 11 May 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.00438, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p11

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

bipartite graphsrainbow matchings

Mathematics Subject Classification ID

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

Abstract: A conjecture by Aharoni and Berger states that every family of $n$ matchings of size $n+1$ in a bipartite multigraph contains a rainbow matching of size $n$. In this paper we prove that matching sizes of $(3/2+o(1))n$ suffice to guarantee such a rainbow matching, which is asymptotically the same bound as the best known one in case we only aim to find a rainbow matching of size $n-1$. This improves previous results by Aharoni, Charbit and Howard, and Kotlar and Ziv.

Recommendations

• Rainbow matchings in bipartite multigraphs
• Rainbow matchings in properly colored multigraphs
• Large matchings in bipartite graphs have a rainbow matching
• Rainbow matchings and rainbow connectedness
• A better bound on the size of rainbow matchings

Cites work

• scientific article; zbMATH DE number 3613053 (Why is no real title available?)
• scientific article; zbMATH DE number 3443668 (Why is no real title available?)
• An n n Latin square has a transversal with at least n- n distinct symbols
• Combinatorial matrix theory
• Large matchings in bipartite graphs have a rainbow matching
• On a generalization of the Ryser-Brualdi-Stein conjecture
• Rainbow matchings and transversals
• Rainbow matchings in r-partite r-graphs
• Rainbow sets in the intersection of two matroids
• Transversals in row-latin rectangles
• Transversals of latin squares and their generalizations

Cited in

(13)

• How many colors guarantee a rainbow matching?
• Representation of large matchings in bipartite graphs
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Fair representation in the intersection of two matroids
• Badges and rainbow matchings
• A better bound on the size of rainbow matchings
• Full rainbow matchings in graphs and hypergraphs
• On sets not belonging to algebras and rainbow matchings in graphs
• Large matchings in bipartite graphs have a rainbow matching
• Rainbow paths and large rainbow matchings
• Rainbow matchings and rainbow connectedness
• Rainbow perfect matchings in \(r\)-partite graph structures
• An approximate version of a conjecture of Aharoni and Berger

This page was built for publication: An improved bound on the sizes of matchings guaranteeing a rainbow matching

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