|Title:||An improved bound on the sizes of matchings guaranteeing a rainbow matching||Language:||English||Authors:||Clemens, Dennis
|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
checked on Jul 6, 2022
Add Files to Item
Note about this record
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.