PreprintCC0arXiv
Exact three-component covers in 2-coloured random bipartite graphs
Abstract
We resolve the two-colour three-component conjecture of Fernández, Pavez-Signé and Stein for random bipartite graphs. More precisely, we prove that if G∼ G(n,n,p) and p≫√(log n/n), then with high probability every red--blue edge-colouring of G admits a cover of its vertex set by at most three monochromatic connected components. The proof is based on a uniform expansion lemma for unions of common neighbourhoods and an alternating common-neighbourhood expansion argument.
Related
- When are random regular triangle-free graphs bipartite?
- FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
- Structural stability of systems and cycle covers in random graphs
- Perron-Wright asymptotics and critical component processes for regular inhomogeneous random graphs
- Rainbow spanning configurations in uniformly coloured pseudorandom graphs
BibTeX
@misc{liu2026exact,
title = {{Exact three-component covers in 2-coloured random bipartite graphs}},
author = {Xiao-Chuan Liu and Xu Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17567},
eprint = {2609.17567},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17567},
note = {CC0},
}
RIS
TY - UNPB
TI - Exact three-component covers in 2-coloured random bipartite graphs
AU - Xiao-Chuan Liu
AU - Xu Yang
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.17567
UR - https://arxiv.org/abs/2609.17567
AB - We resolve the two-colour three-component conjecture of Fernández, Pavez-Signé and Stein for random bipartite graphs. More precisely, we prove that if G∼ G(n,n,p) and p≫√(log n/n), then with high probability every red--blue edge-colouring of G admits a cover of its vertex set by at most three monochromatic connected components. The proof is based on a uniform expansion lemma for unions of common neighbourhoods and an alternating common-neighbourhood expansion argument.
ER -