Given two graphs G and H, let f(G,H) denote the maximum number c for which there is a way to color the edges of G with c colors such that every subgraph H of G has at least two edges of the same color. Equivalently, any edge-coloring of G with at least rb(G,H)=f(G,H)+1 colors contains a rainbow copy of H, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number rb(G,H) is called the rainbow number of H with respect to G, and simply called the bipartite rainbow number of H if G is the complete bipartite graph Km,n. Erdős, Simonovits and Sós showed that rb(Kn,K3)=n. In 2004, Schiermeyer determined the rainbow numbers rb(Kn,Kk) for all n≥k≥4, and the rainbow numbers rb(Kn,kK2) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(Km,n,kK2) for all k≥1.
Financed by the National Centre for Research and Development under grant No. SP/I/1/77065/10 by the strategic scientific research and experimental development program:
SYNAT - “Interdisciplinary System for Interactive Scientific and Scientific-Technical Information”.