Large monochromatic components in multicolored bipartite graphs

It is well known that in every r ‐coloring of the edges of the complete bipartite graph K m , nthere 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 , δ ( X , Y ) > ( 1 − 1 / ( r + 1 )) n , and δ ( 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.