A proof of a conjecture of Erdős and Gyárfás on monochromatic path covers
In 1995, Erdős and Gyárfás proved that in every 2-edge-coloured complete graph on n vertices, there exists a collection of 2 n monochromatic paths, all of the same colour, which cover the entire vertex set. They conjectured that it is possible to replace 2 n by n . We prove this to be true for all sufficiently large n .
Authors
- Alexey Pokrovskiy (ORCID: https://orcid.org/0000-0002-8989-3962)
- Leo Versteegen (ORCID: https://orcid.org/0000-0001-7278-3284)
- Ella Williams
Institutions
- University College London (GB)
Publication Details
- Journal
- Journal of Combinatorial Theory Series B
- Published
- 2025-10-29
- DOI
- https://doi.org/10.1016/j.jctb.2025.10.007
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00