Given an edge-colored graph G = (V,E), a rainbow matching M in G is a set of pairwise non-adjacent edges, that is, no two edges share a common vertex, such that all the edges in the set have distinct colors.
A maximum rainbow matching is a rainbow matching that contains the largest possible number of edges.
Rainbow matchings are of particular interest given their connection to transversals of Latin squares. For complete bipartite graphs, every proper n-edge coloring of Kn,n corresponds to a Latin square of order n. A rainbow matching then corresponds to a Latin transversal of the Latin square, meaning a selection of n positions, one in each row and each column, containing distinct entries. This connection between Latin transversals and rainbow matchings in Kn,n has inspired additional interest in the study of rainbow matchings in triangle-free graphs.
Wang asked if there is a function f(δ) such that a properly edge-colored graph G with minimum degree δ and order at least f(δ) must have a rainbow matching of size δ. Diemunsch, et. al. answered this question in the affirmitive and showed that given a properly edge-colored graph G with minimum degree δ and order at least f(δ) = 98δ/23, there exists a rainbow matching of size δ in G. This bound was later improved to f(δ) = 4δ − 3 by Andras Gyarfas and Gabor N. Sarkozy. This is the best known estimate to date.
- West, D.B. (2009), Rainbow Matchings
- Garey, M. R.; Johnson, D. S. (1979). Victor Klee, ed. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5. MR 519066.
- Wang, Guanghui (2009), "Rainbow Matchings in Properly Edge Colored Graphs", The Electronic Journal of Combinatorics 18 (1): 162
- Diemunsch, Jennifer; Ferrara, Michael; Lo, Allan; Moffatt, Casey; Pfender, Florian; Wenger, Paul S. (2012), "Rainbow Matchings of Size δ(G) in Properly Edge-Colored Graphs", The Electronic Journal of Combinatorics 19 (2): 52
- Gyarfas, Andras; Sarkozy, Gabor N. (2012). "Rainbow matchings and partial transversals of Latin squares". arXiv:1208.5670 [CO math. CO].