Sách Rainbow Matching in Edge-Colored Graphs

Abstract
A rainbow subgraph of an edge-colored graph is a subgraph whose edges have
distinct colors. The color degree of a vertex v is the number of different colors on
edges incident to v. Wang and Li conjectured that for k > 4, every edge-colored
graph with minimum color degree at least k contains a rainbow matching of size
at least ⌈ k/2⌉ . We prove the slightly weaker statement that a rainbow matching of
size at least ⌊ k/2⌋ is guaranteed. We also give sufficient conditions for a rainbow
matching of size at least ⌈k/2⌉ that fail to hold only for finitely many exceptions
(for each odd k).