On monochromatic path covers conjecture of Erdős--Gyárfás

Hangdi Chen; Yaojun Chen

paper

On monochromatic path covers conjecture of Erdős--Gyárfás

arXiv:2607.21915

Abstract

Erdős and Gyárfás conjectured in 1995 that, in every red--blue edge-coloring of a complete graph $K_{n}$ , the vertex set can be covered by at most $n$ monochromatic paths, all of the same color. Pokrovskiy, Versteegen and Williams (JCT-B, 2026) proved the conjecture for all sufficiently large $n$ . In this paper, by using minimal counterexample method, we confirm the conjecture completely.