Titel: An improved bound on the sizes of matchings guaranteeing a rainbow matching
Sprache: Englisch
Autor/Autorin: Clemens, Dennis  
Ehrenmüller, Julia 
Schlagwörter: Bipartite graphs; Rainbow matchings
Erscheinungs­datum: 15-Apr-2016
Quellenangabe: Electronic Journal of Combinatorics 2 (23): P2.11 (2016-04-15)
Zusammenfassung (englisch): 
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
Zeitschrift: The journal of combinatorics 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Enthalten in den Sammlungen:Publications without fulltext

Zur Langanzeige

Seitenansichten

66
Letzte Woche
1
Letzten Monat
0
checked on 01.10.2022

Google ScholarTM

Prüfe

Volltext ergänzen

Feedback zu diesem Datensatz

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.