Geodesic
Rainbow paths and large rainbow matchings
Ron Aharoni1 ; Eli Berger ; Maria Chudnovsky ; Shira Zerbib2
1Technion
2Iowa State University
The electronic journal of combinatorics, Tome 29 (2022) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A conjecture of the first two authors is that $n$ matchings of size $n$ in any graph have a rainbow matching of size $n-1$. We prove a lower bound of $\frac{2}{3}n-1$, improving on the trivial $\frac{1}{2}n$, and an analogous result for hypergraphs. For $\{C_3,C_5\}$-free graphs and for disjoint matchings we obtain a lower bound of $\frac{3n}{4}-O(1)$. We also discuss a conjecture on rainbow alternating paths, that if true would yield a lower bound of $n-\sqrt{2n}$. We prove the non-alternating (ordinary paths) version of this conjecture.
DOI : 10.37236/10173
Classification : 05C70, 05D15, 05C15, 05C38, 05C65
Mots-clés : \(\{C_3,C_5\} \)-free graphs, S-rainbow set, \(r\)-uniform hypergraphs

Ron Aharoni  1   ; Eli Berger    ; Maria Chudnovsky    ; Shira Zerbib  2

1 Technion
2 Iowa State University 
@article{10_37236_10173,
     author = {Ron Aharoni and Eli  Berger and Maria Chudnovsky and Shira Zerbib},
     title = {Rainbow paths and large rainbow matchings},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {1},
     doi = {10.37236/10173},
     zbl = {1481.05122},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10173/}
}
TY  - JOUR
AU  - Ron Aharoni
AU  - Eli  Berger
AU  - Maria Chudnovsky
AU  - Shira Zerbib
TI  - Rainbow paths and large rainbow matchings
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10173/
DO  - 10.37236/10173
ID  - 10_37236_10173
ER  - 
%0 Journal Article
%A Ron Aharoni
%A Eli  Berger
%A Maria Chudnovsky
%A Shira Zerbib
%T Rainbow paths and large rainbow matchings
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10173/
%R 10.37236/10173
%F 10_37236_10173
Ron Aharoni; Eli  Berger; Maria Chudnovsky; Shira Zerbib. Rainbow paths and large rainbow matchings. The electronic journal of combinatorics, Tome 29 (2022) no. 1. doi: 10.37236/10173

Cité par Sources :