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