Monochromatic Partitions in 2-Edge-Coloured Bipartite Graphs

Abstract

We study two variations of the Gyárfás-Lehel conjecture on the minimum number of monochromatic components needed to cover an edge-coloured complete bipartite graph. Specifically, we show the following.

• For $p\gg (\log n/n)^{1/2}$, w.h.p. every $2$-colouring of the random bipartite graph $G\sim G(n,n,p)$ admits a cover of all but $O(1/p)$ vertices of $G$ using at most three vertex-disjoint monochromatic components.
• For every 2-colouring of a bipartite graph $G$ with parts of size $n$ and minimum degree $(13/16+o(1))n$, the vertices of $G$ can be covered using at most three vertex-disjoint monochromatic components.