Rainbow matching in edge-colored graphs (Q976680): Difference between revisions

Summary: 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\). \textit{G. Wang} and \textit{H. Li} [``Heterochromatic matchings in edge-colored graphs'', Electron. J. Comb. 15, No.\,1, Research Paper R138 (2008; Zbl 1165.05330)] conjectured that for \(k \geqslant 4\), every edge-colored graph with minimum color degree at least \(k\) contains a rainbow matching of size at least \(\lceil k/2\rceil \). We prove the slightly weaker statement that a rainbow matching of size at least \(\lfloor k/2\rfloor\) is guaranteed. We also give sufficient conditions for a rainbow matching of size at least \(\lceil k/2\rceil\) that fail to hold only for finitely many exceptions (for each odd \(k\)).