Superlinear Lower Bounds for Monochromatic Path Partitions

Abstract

In 1989, Gyárfás conjectured that the vertex set of every $r$-edge-coloured complete graph can be partitioned into at most $r$ vertex-disjoint monochromatic paths. Erdős, Gyárfás, and Pyber subsequently proposed the analogous conjecture for monochromatic cycles. Pokrovskiy proved Gyárfás's conjecture for $r=3$, while disproving the conjecture of Erdős, Gyárfás, and Pyber for every $r\ge 3$ by constructing colourings that require at least $r+1$ monochromatic cycles. In this paper, we disprove Gyárfás's conjecture in a quantitatively strong superlinear form: for every sufficiently large $r$, there exists an $r$-edge-coloured complete graph that requires at least $(1-o(1))r\log \log r$ vertex-disjoint monochromatic paths. Consequently, the monochromatic cycle-partition number is also superlinear in $r$. Our construction also disproves two conjectures of Pokrovskiy: one on monochromatic cycle coverings and the other on path coverings in the balanced bipartite setting.

17 pages; added new results