Pokrovksiy, Alexey;
Versteegen, Leo;
Williams, Ella;
(2026)
A proof of a conjecture of Erdős and Gyárfás on monochromatic path covers.
Journal of Combinatorial Theory, Series B
, 176
pp. 551-560.
10.1016/j.jctb.2025.10.007.
![[thumbnail of Monochromatic_path_covers (14).pdf]](https://discovery.ucl.ac.uk/style/images/fileicons/text.png) |
Text
Monochromatic_path_covers (14).pdf - Accepted Version Access restricted to UCL open access staff until 30 October 2026. Download (268kB) |
Abstract
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 2n monochromatic paths, all of the same colour, which cover the entire vertex set. They conjectured that it is possible to replace 2n by n. We prove this to be true for all sufficiently large n.
| Type: | Article |
|---|---|
| Title: | A proof of a conjecture of Erdős and Gyárfás on monochromatic path covers |
| DOI: | 10.1016/j.jctb.2025.10.007 |
| Publisher version: | https://doi.org/10.1016/j.jctb.2025.10.007 |
| Language: | English |
| Additional information: | ArXiv version: https://arxiv.org/pdf/2409.03623 |
| Keywords: | Ramsey theory, Graph partitioning, Paths |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10219253 |
Archive Staff Only
 |
View Item |
