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

zbMATH Open1335.05137arXiv1503.00438MaRDI QIDQ281599FDOQ281599

Authors: Dennis Clemens, Julia Ehrenmüller 

Publication date: 11 May 2016

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

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.

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

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

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

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)

Cites Work

• Transversals of latin squares and their generalizations
• An \(n\times n\) Latin square has a transversal with at least \(n-\sqrt n\) distinct symbols
• Rainbow matchings in \(r\)-partite \(r\)-graphs
• Rainbow sets in the intersection of two matroids
• Combinatorial matrix theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Transversals in row-latin rectangles
• Large matchings in bipartite graphs have a rainbow matching
• Rainbow matchings and transversals
• On a generalization of the Ryser-Brualdi-Stein conjecture

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)