Geodesic
Heterochromatic matchings in edge-colored graphs
The electronic journal of combinatorics, Tome 15 (2008)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $G$ be an (edge-)colored graph. A heterochromatic matching of $G$ is a matching in which no two edges have the same color. For a vertex $v$, let $d^c(v)$ be the color degree of $v$. We show that if $d^c(v)\geq k$ for every vertex $v$ of $G$, then $G$ has a heterochromatic matching of size $\big\lceil{5k-3\over 12}\big\rceil$. For a colored bipartite graph with bipartition $(X,Y)$, we prove that if it satisfies a Hall-like condition, then it has a heterochromatic matching of cardinality $\big\lceil{|X|\over 2}\big\rceil$, and we show that this bound is best possible.
DOI : 10.37236/862
Classification : 05C38, 05C15
Mots-clés : heterochromatic matching, edge coloring 
@article{10_37236_862,
     author = {Guanghui Wang and Hao Li},
     title = {Heterochromatic matchings in edge-colored graphs},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/862},
     zbl = {1165.05330},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/862/}
}
TY  - JOUR
AU  - Guanghui Wang
AU  - Hao Li
TI  - Heterochromatic matchings in edge-colored graphs
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/862/
DO  - 10.37236/862
ID  - 10_37236_862
ER  - 
%0 Journal Article
%A Guanghui Wang
%A Hao Li
%T Heterochromatic matchings in edge-colored graphs
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/862/
%R 10.37236/862
%F 10_37236_862
Guanghui Wang; Hao Li. Heterochromatic matchings in edge-colored graphs. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/862

Cité par Sources :