A Rainbow k-Matching in the Complete Graph with r Colors
A Rainbow k-Matching in the Complete Graph with r Colors
复制标题
DOI：
10.37236/140
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
S. Fujita;A. Kaneko;I. Schiermeyer;Kazuhiro Suzuki
中科院分区：
文献类型：
--
作者：
S. Fujita;A. Kaneko;I. Schiermeyer;Kazuhiro Suzuki
一个图的$r$-边染色是将$r$种颜色赋给图的边。一个图的正$r$-边染色是一个使用所有$r$颜色的图的$r$-边染色。边着色图的匹配称为彩虹匹配，如果在匹配中没有两条边具有相同的颜色。本文证明了一个n阶r-边着色完全图有大小为k（\ge 2）的彩虹匹配，如果r \gemax\{{2k-3\choose 2}+2，{k-2\choose 2}+（k-2）（n-k+2）+2 \}，k \ge 2$，和n \ge 2k+1$. $r$上的边界是最好的。
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.