**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
*d ^{c}(v)* to denote the

**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

**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

**Comments:**
Proper edge-colorings of complete graphs show that Conjecture 3 is sharp if
true. Li and Wang [LW] proved that
*&alpha _{c}'(G)≥*⌈

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 *K _{4}* 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?

**References:**

[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.