Geodesic
An improved bound on the sizes of matchings guaranteeing a rainbow matching
Dennis Clemens1 ; Julia Ehrenmüller1
1Technische Universität Hamburg
The electronic journal of combinatorics, Tome 23 (2016) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 $\left(\frac 3 2 + o(1)\right) 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.
DOI : 10.37236/5080
Classification : 05C70, 05C15, 05D15
Mots-clés : rainbow matchings, bipartite graphs

Dennis Clemens  1   ; Julia Ehrenmüller  1

1 Technische Universität Hamburg 
@article{10_37236_5080,
     author = {Dennis Clemens and Julia Ehrenm\"uller},
     title = {An improved bound on the sizes of matchings guaranteeing a rainbow matching},
     journal = {The electronic journal of combinatorics},
     year = {2016},
     volume = {23},
     number = {2},
     doi = {10.37236/5080},
     zbl = {1335.05137},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/5080/}
}
TY  - JOUR
AU  - Dennis Clemens
AU  - Julia Ehrenmüller
TI  - An improved bound on the sizes of matchings guaranteeing a rainbow matching
JO  - The electronic journal of combinatorics
PY  - 2016
VL  - 23
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/5080/
DO  - 10.37236/5080
ID  - 10_37236_5080
ER  - 
%0 Journal Article
%A Dennis Clemens
%A Julia Ehrenmüller
%T An improved bound on the sizes of matchings guaranteeing a rainbow matching
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/5080/
%R 10.37236/5080
%F 10_37236_5080
Dennis Clemens; Julia Ehrenmüller. An improved bound on the sizes of matchings guaranteeing a rainbow matching. The electronic journal of combinatorics, Tome 23 (2016) no. 2. doi: 10.37236/5080

Cité par Sources :