Large monochromatic components in multicolored bipartite graphs

It is well known that in every r-coloring of the edges of the complete bipartite graph Km,n there is a monochromatic connected component with at least (m+n)/r vertices. In this paper we study an extension of this problem by replacing complete bipartite graphs by bipartite graphs of large minimum degree. We conjecture that in every r-coloring of the edges of an (X,Y)-bipartite graph with |X|=m,|Y|=n,delta(X,Y)>(1-1/(r+1))n, and delta(Y,X)>(1-1/(r+1))m, there exists a monochromatic component on at least (m+n)/r vertices (as in the complete bipartite graph). If true, the minimum degree condition is sharp (in that both inequalities cannot be made weak when m and n are divisible by r+1). We prove the conjecture for r = 2 and we prove a weaker bound for all r >= 3. As a corollary, we obtain a result about the existence of monochromatic components with at least n/(r - 1) vertices in r-colored graphs with large minimum degree.