A Rainbow k-Matching in the Complete Graphwith r Colors

摘要

An r-edge-coloring of a graph is an assignment of r colors to the edges of thegraph. An exactly r-edge-coloring of a graph is an r-edge-coloring of the graph thatuses 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 thatan exactly r-edge-colored complete graph of order n has a rainbow matching of sizek(≥ 2) if r ≥ max{ {2k2-3) +2, (k2-2)(2)(—+2) 21,k 2, and n ≥ 2k + 1.The bound on r is best possible.