Geodesic
Rainbow matching in edge-colored graphs
The electronic journal of combinatorics, Tome 17 (2010)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A rainbow subgraph of an edge-colored graph is a subgraph whose edges have distinct colors. The color degree of a vertex $v$ is the number of different colors on edges incident to $v$. Wang and Li conjectured that for $k\geq 4$, every edge-colored graph with minimum color degree at least $k$ contains a rainbow matching of size at least $\left\lceil k/2 \right\rceil$. We prove the slightly weaker statement that a rainbow matching of size at least $\left\lfloor k/2 \right\rfloor$ is guaranteed. We also give sufficient conditions for a rainbow matching of size at least $\left\lceil k/2 \right\rceil$ that fail to hold only for finitely many exceptions (for each odd $k$).
DOI : 10.37236/475
Classification : 05C15, 05C35, 05C55, 05C70
Mots-clés : rainbow subgraph, color degree 
@article{10_37236_475,
     author = {Timothy D. LeSaulnier and Christopher Stocker and Paul S. Wenger and Douglas B. West},
     title = {Rainbow matching in edge-colored graphs},
     journal = {The electronic journal of combinatorics},
     year = {2010},
     volume = {17},
     doi = {10.37236/475},
     zbl = {1188.05063},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/475/}
}
TY  - JOUR
AU  - Timothy D. LeSaulnier
AU  - Christopher Stocker
AU  - Paul S. Wenger
AU  - Douglas B. West
TI  - Rainbow matching in edge-colored graphs
JO  - The electronic journal of combinatorics
PY  - 2010
VL  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.37236/475/
DO  - 10.37236/475
ID  - 10_37236_475
ER  - 
%0 Journal Article
%A Timothy D. LeSaulnier
%A Christopher Stocker
%A Paul S. Wenger
%A Douglas B. West
%T Rainbow matching in edge-colored graphs
%J The electronic journal of combinatorics
%D 2010
%V 17
%U http://geodesic.mathdoc.fr/articles/10.37236/475/
%R 10.37236/475
%F 10_37236_475
Timothy D. LeSaulnier; Christopher Stocker; Paul S. Wenger; Douglas B. West. Rainbow matching in edge-colored graphs. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/475

Cité par Sources :