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. Denote by Kn,n the complete bipartite graph on n + n vertices. Every proper n-edge coloring of Kn,n corresponds to a Latin square of order n. A rainbow matching then corresponds to a transversal of the Latin square, meaning a selection of n positions, one in each row and each column, containing distinct entries. This connection between transversals of Latin squares and rainbow matchings in Kn,n has inspired additional interest in the study of rainbow matchings in triangle-free graphs.
Existence when each edge has a single color An edge-coloring is called proper if each edge has a single color, and each two edges of the same color have no vertex in common. A proper edge-coloring does not guarantee the existence of a perfect rainbow matching. For example, consider the graph K2,2: the complete bipartite graph on 2+2 vertices. Suppose the edges (x1,y1) and (x2,y2) are colored green, and the edges (x1,y2) and (x2,y1) are colored blue. This is a proper coloring, but there are only two perfect matchings, and each of them is colored by a single color. This invokes the question: when does a large rainbow matching is guaranteed to exist?
Bounds depending only on the number of vertices Much of the research on this question was published using the terminology of Latin transversals in Latin squares. Translated into the rainbow matching terminology: In 1967, H. J. Ryser conjectured that, when n is odd, every proper edge-coloring of Kn,n has a rainbow matching of size n. In 1975, S. K. Stein and Brualdi conjectured that, when n is even, every proper edge-coloring of Kn,n has a rainbow matching of size n – 1. (it is known that a rainbow matching of size n need not exist in this case). A more general conjecture of Stein is that a rainbow matching of size n – 1 exists not only for a proper edge-coloring, but for any coloring in which each color appears on exactly n edges. Some weaker versions of these conjectures have been proved:
Every proper edge-coloring of Kn,n has a rainbow matching of size 2n/3. Every proper edge-coloring of Kn,n has a rainbow matching of size n − n . {\displaystyle n-{\sqrt {n}}.} Every proper edge-coloring of Kn,n has a rainbow matching of size n – 11 log22(n). Every proper edge-coloring of Kn,n has a rainbow matching of size n – O(log n/log log n). Every proper edge-coloring of Kn,n has a rainbow matching of size n – 1. (Preprint)
Bounds depending on the minimum degree Wang asked if there is a function f(d) such that every properly edge-colored graph G with minimum degree d and at least f(d) vertices must have a rainbow matching of size d. Obviously at least 2d vertices are necessary, but how many are sufficient?
Diemunsch, et al. answered this question in the affirmative and showed that given a properly edge-colored graph G with minimum degree d and order at least f(d) = 13d/2−23/2+41/(8d), there exists a rainbow matching of size d in G. This bound was later improved to f(d) = 4d – 3 by Andras Gyarfas and Gabor N. Sarkozy. They also show that any graph with at least 2d vertices has a rainbow matching of size at least d – 2d2/3. These are the best known estimate to date.
Existence when the same edge may have different colors Suppose that each edge may have several different colors, while each two edges of the same color must still have no vertex in common. In other words, each color is a matching. How many colors are needed in order to guarantee the existence of a rainbow matching?
In complete bipartite graphs Drisko studied this question using the terminology of Latin rectangles. He proved that, for any n ≤ k, in the complete bipartite graph Kn,k, any family of 2n – 1 matchings (=colors) of size n has a perfect rainbow matching (of size n). He applied this theorem to questions about group actions and difference sets. Drisko also showed that 2n – 1 matchings may be necessary: consider a family of 2n – 2 matchings, of which n – 1 are { (x1, y1), (x2, y2), ..., (xn, yn)} and the other n – 1 are {(x1, y2), (x2, y3), …, (xn, y1) }. Then the largest rainbow matching is of size n – 1 (e.g. take one edge from each of the first n – 1 matchings). Alon showed that Drisko's theorem implies an older result in additive number theory.
In general bipartite graphs Aharoni and Berger generalized Drisko's theorem to any bipartite graph, namely: any family of 2n – 1 matchings of size n in a bipartite graph has a rainbow matching of size n. Aharoni, Kotlar and Ziv showed that Drisko's extremal example is unique in any bipartite graph.
In general graphs In general graphs, 2n – 1 matchings are no longer sufficient. When n is even, one can add to Drisko's example the matching { (x1, x2), (y1, y2), (x2, x3), (y2, y3), … } and get a family of 2n – 1 matchings without any rainbow matching. Aharoni, Berger, Chudnovsky, Howard and Seymour proved that, in a general graph, 3n – 2 matchings (=colors) are always sufficient. It is not known whether this is tight: currently the best lower bound for even n is 2n and for odd n it is 2n – 1.
Rainbow fractional matchings A fractional matching is a set of edges with a non-negative weight assigned to each edge, such that the sum of weights adjacent to each vertex is at most 1. The size of a fractional matching is the sum of weights of all edges. It is a generalization of a matching, and can be used to generalize both the colors and the rainbow matching:
… excerpt ends here. Continue reading the full article.
