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

  1. ↑ West, D.B. (2009), Rainbow Matchings
  2. ↑ 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.
  3. ↑ Wang, Guanghui (2009), "Rainbow Matchings in Properly Edge Colored Graphs", The Electronic Journal of Combinatorics 18 (1): 162
  4. ↑ 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
  5. ↑ Gyarfas, Andras; Sarkozy, Gabor N. (2012). "Rainbow matchings and partial transversals of Latin squares". arXiv:1208.5670 [CO math. CO].
This article is issued from Wikipedia - version of the Monday, July 28, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.