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

2026/07/24 by Hangdi Chen, Yaojun Chen
#math.CO

paper · pdf

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.

Related

• A proof of a conjecture of Erdős and Gyárfás on monochromatic path covers
• Vertex covering with monochromatic pieces of few colours
• Monochromatic loose path partitions in k-uniform hypergraphs
• Partitioning edge-coloured complete graphs into monochromatic cycles and\n paths
• Erdős-Gallai-type results for colorful monochromatic connectivity of a graph