A rainbow \(k\)-matching in the complete graph with \(r\) colors (Q1028829)

Summary: 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(\geq 2)\) if \(r\geq\max\big\{\binom{3k-3}{2}+2, \binom{k-2}{2}+ (k-2)(n-k+2)+2\big\}\), \(k\geq 2\), and \(n\geq 2k+1\). The bound on \(r\) is best possible.