Geodesic
A rainbow \(k\)-matching in the complete graph with \(r\) colors
The electronic journal of combinatorics, Tome 16 (2009) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

An $r$-edge-coloring of a graph is an assignment of $r$ colors to the edges of the graph. An exactly $r$-edge-coloring of a graph is an $r$-edge-coloring of the graph that uses all $r$ colors. A matching of an edge-colored graph is called rainbow matching, if no two edges have the same color in the matching. In this paper, we prove that an exactly $r$-edge-colored complete graph of order $n$ has a rainbow matching of size $k(\ge 2)$ if $r \ge max\{{2k-3\choose 2}+2, {k-2\choose 2}+(k-2)(n-k+2)+2 \}$, $k \ge 2$, and $n \ge 2k+1$. The bound on $r$ is best possible.
DOI : 10.37236/140
Classification : 05C15
Mots-clés : edge-coloring, rainbow matching, complete graph, anti-Ramsey, heterochromatic, totally multicolored 
@article{10_37236_140,
     author = {Shinya Fujita and Atsushi Kaneko and Ingo Schiermeyer and Kazuhiro Suzuki},
     title = {A rainbow \(k\)-matching in the complete graph with \(r\) colors},
     journal = {The electronic journal of combinatorics},
     year = {2009},
     volume = {16},
     number = {1},
     doi = {10.37236/140},
     zbl = {1181.05040},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/140/}
}
TY  - JOUR
AU  - Shinya Fujita
AU  - Atsushi Kaneko
AU  - Ingo Schiermeyer
AU  - Kazuhiro Suzuki
TI  - A rainbow \(k\)-matching in the complete graph with \(r\) colors
JO  - The electronic journal of combinatorics
PY  - 2009
VL  - 16
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/140/
DO  - 10.37236/140
ID  - 10_37236_140
ER  - 
%0 Journal Article
%A Shinya Fujita
%A Atsushi Kaneko
%A Ingo Schiermeyer
%A Kazuhiro Suzuki
%T A rainbow \(k\)-matching in the complete graph with \(r\) colors
%J The electronic journal of combinatorics
%D 2009
%V 16
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/140/
%R 10.37236/140
%F 10_37236_140
Shinya Fujita; Atsushi Kaneko; Ingo Schiermeyer; Kazuhiro Suzuki. A rainbow \(k\)-matching in the complete graph with \(r\) colors. The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/140

Cité par Sources :