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.
Fields of Study & Subjects
Graph Labeling and Dimension Problems
Graph theory and applications
Publication details
- Journal / source
- The Electronic Journal of Combinatorics
- Volume
- 33
- Issue
- 1
- Publication date
- 9 January 2026
- Language
- EN