Rainbow matching
In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.
Definition
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.
History
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.[1]
Garey and Johnson have shown that computing a maximum matching is NP-complete even for edge-colored bipartite graphs.[2] Thus, the attention shifted to study "external problems".
Results
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 δ.[3] 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.[4] This bound was later improved to f(δ) = 4δ − 3 by Andras Gyarfas and Gabor N. Sarkozy.[5] This is the best known estimate to date.
See also
References
- ^ 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 0519066.
{{cite book}}: Invalid|ref=harv(help) - ^ 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].