Rainbow Matchings (2008)

Originators: H. Li and G. Wang    (presented by D.B. West - REGS 2009)

Definitions: In an edge-colored graph, a rainbow or heterochromatic subgraph is a subgraph whose edges have distinct colors (also called polychromatic or totally multicolored in the literature). Li and Wang [LW] use dc(v) to denote the color degree of a vertex v, which is the number of edges in the largest rainbow star centered at v. Let δc(G) denote the smallest color degree among all vertices in an edge-colored graph G.

Background: It is natural to seek the largest rainbow subgraphs of various types that are forced by various conditions on an edge-coloring. A survey of results on rainbow subgraphs appears in [KL]. Here we consider rainbow matchings. Let αc'(G) denote the maximum size of a rainbow matching in a given edge-colored graph G. Garey and Johnson [GJ] showed that computing αc'(G) is NP-complete even for edge-colored bipartite graphs (the edge-coloring is part of the input). Therefore, we study extremal problems. Two possible ways to guarantee large rainbow matchings are to require the edge-coloring to be a proper edge-coloring (then the color degree at each vertex is its number of neighbors) or to require large minimum color degree. Woolbright and Fu ([WF]) showed that every proper (2n-1)-edge-coloring of K2n has a rainbow perfect matching. For complete bipartite graphs, every proper n-edge-coloring of Kn,n corresponds to a latin square of order n; a rainbow matching corresponds to a latin transversal of the latin square, meaning a selection of one position in each row and column containing distinct labels.

Conjecture 1 (Ryser [R]): Every latin square of odd order has a latin transversal.

Conjecture 2 (Brualdi [unpubl.], Stein [St]): Every latin square of order n has a partial latin transversal of size at least n-1.

Comments: A partial latin transversal of size k corresponds to a rainbow matching of size k. Shor [Sh] proved that there is always a partial latin transversal (rainbow matching) of size at least n-5.53(log n).

Conjecture 3 (Wang-Li [WL]): If G is an edge-colored graph with δc(G)=k, then &alphac'(G)≥k/2⌉.

Comments: Proper edge-colorings of complete graphs show that Conjecture 3 is sharp if true. Li and Wang [LW] proved that &alphac'(G)≥2k/3⌉ when G is an edge-colored bipartite graph such that δc(G)=k≥3. Toward Conjecture 3 for general graphs, they proved that &alphac'(G)≥(5k-3)/12⌉.

One can also define the rainbow edge-chromatic number of an edge-colored multigraph to be the minimum number of rainbow matchings whose union is G. When K4 is given a proper edge-coloring, the rainbow edge-chromatic number is 6.

Question 4: What is the best bound on the rainbow edge-chromatic number in terms of the maximum color degree?

[GJ] Garey, Michael R.; Johnson, David S. Computers and intractability: A guide to the theory of NP-completeness. A Series of Books in the Mathematical Sciences. W. H. Freeman and Co., San Francisco, Calif., 1979. x+338 pp., Problem GT55.
[KL] Kano, Mikio; Li, Xueliang Monochromatic and heterochromatic subgraphs in edge-colored graphs---a survey. Graphs Combin. 24 (2008), no. 4, 237--263.
[LW] Li, Hao; Wang, Guanghui Color degree and heterochromatic matchings in edge-colored bipartite graphs. Util. Math. 77 (2008), 145--154.
[R] Ryser, H.J. Neuere probleme der kombinatorik, in "Vortrage uber Kombinatorik Oberwolfach", Mathematisches Forschungsinstitut Oberwolfach, July 1967, 24-29.
[Sh] Shor, P. W. A lower bound for the length of a partial transversal in a Latin square. J. Combin. Theory Ser. A 33 (1982), no. 1, 1--8.
[St] Stein, S. K. Transversals of Latin squares and their generalizations. Pacific J. Math. 59 (1975), no. 2, 567--575.
[WL] Wang, Guanghui; Li, Hao Heterochromatic matchings in edge-colored graphs. Electron. J. Combin. 15 (2008), no. 1, Research Paper 138, 10 pp.
[WF] Woolbright, David E.; Fu, Hung-Lin On the existence of rainbows in $1$-factorizations of $K\sb {2n}$. J. Combin. Des. 6 (1998), no. 1, 1--20.