Title: An improved bound on the sizes of matchings guaranteeing a rainbow matching
Language: English
Authors: Clemens, Dennis  
Ehrenmüller, Julia 
Keywords: Bipartite graphs; Rainbow matchings
Issue Date: 15-Apr-2016
Source: Electronic Journal of Combinatorics 2 (23): P2.11 (2016-04-15)
Abstract (english): 
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 the case where 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.
URI: http://hdl.handle.net/11420/5949
ISSN: 2156-3527
Journal: The journal of combinatorics 
Institute: Mathematik E-10 
Document Type: Article
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Jul 6, 2022

Google ScholarTM


Add Files to Item

Note about this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.