Geodesic
Rainbow matchings of size \(\delta(G)\) in properly edge-colored graphs
Jennifer Diemunsch1 ; Michael Ferrara1 ; Allan Lo2 ; Casey Moffatt1 ; Florian Pfender3 ; Paul S Wenger1
1University of Colorado Denver
2Univeristy of Birmingham
3Universität Rostock
The electronic journal of combinatorics, Tome 19 (2012) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors. Wang asked if there is a function $f(\delta)$ such that a properly edge-colored graph $G$ with minimum degree $\delta$ and order at least $f(\delta)$ must have a rainbow matching of size $\delta$. We answer this question in the affirmative; an extremal approach yields that $f(\delta) = 98\delta/23< 4.27\delta$ suffices. Furthermore, we give an $O(\delta(G)|V(G)|^2)$-time algorithm that generates such a matching in a properly edge-colored graph of order at least $6.5\delta$.
DOI : 10.37236/2443
Classification : 05C70, 05C15
Mots-clés : rainbow matching, properly edge-colored graphs

Jennifer Diemunsch  1   ; Michael Ferrara  1   ; Allan Lo  2   ; Casey Moffatt  1   ; Florian Pfender  3   ; Paul S Wenger  1

1 University of Colorado Denver
2 Univeristy of Birmingham
3 Universität Rostock 
@article{10_37236_2443,
     author = {Jennifer Diemunsch and Michael Ferrara and Allan Lo and Casey Moffatt and Florian Pfender and Paul S Wenger},
     title = {Rainbow matchings of size {\(\delta(G)\)} in properly edge-colored graphs},
     journal = {The electronic journal of combinatorics},
     year = {2012},
     volume = {19},
     number = {2},
     doi = {10.37236/2443},
     zbl = {1253.05113},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2443/}
}
TY  - JOUR
AU  - Jennifer Diemunsch
AU  - Michael Ferrara
AU  - Allan Lo
AU  - Casey Moffatt
AU  - Florian Pfender
AU  - Paul S Wenger
TI  - Rainbow matchings of size \(\delta(G)\) in properly edge-colored graphs
JO  - The electronic journal of combinatorics
PY  - 2012
VL  - 19
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2443/
DO  - 10.37236/2443
ID  - 10_37236_2443
ER  - 
%0 Journal Article
%A Jennifer Diemunsch
%A Michael Ferrara
%A Allan Lo
%A Casey Moffatt
%A Florian Pfender
%A Paul S Wenger
%T Rainbow matchings of size \(\delta(G)\) in properly edge-colored graphs
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2443/
%R 10.37236/2443
%F 10_37236_2443
Jennifer Diemunsch; Michael Ferrara; Allan Lo; Casey Moffatt; Florian Pfender; Paul S Wenger. Rainbow matchings of size \(\delta(G)\) in properly edge-colored graphs. The electronic journal of combinatorics, Tome 19 (2012) no. 2. doi: 10.37236/2443

Cité par Sources :