{"id":"arxiv/2608.09895","url":"https://arxiv.org/abs/2608.09895","tags":["math.CO"],"score":0,"title":"Superlinear Lower Bounds for Monochromatic Path Partitions","domain":"math.CO","source":"arxiv","authors":["Heng Li","Lanchao Wang"],"reviews":0,"subject":"math.CO","summary":"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\\ge3$ 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$,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-10","reactions":{}}