{"id":"arxiv/2601.22117","url":"https://arxiv.org/abs/2601.22117","tags":["math.CO"],"score":0,"title":"Monochromatic cycle partitions of $r$-edge-coloured graphs with high minimum degree","domain":"math.CO","source":"arxiv","authors":["Francesco Di Braccio","Viresh Patel"],"reviews":0,"subject":"math.CO","summary":"A question posed independently by Letzter and Pokrovskiy asks: how many vertex-disjoint monochromatic cycles are needed to cover the vertex set of an $r$-edge-coloured graph, as a function of its minimum (uncoloured) degree? We resolve this problem up to a $(\\log r)$-factor. Specifically, we prove that, for any $r \\geq 2$ and $δ\\in (0,1/2)$, any $n$-vertex $r$-edge-coloured graph $G$ with $δ(G) \\geq (1- δ)n$ can be covered with $\\mathcal{O}(r \\log r \\cdot \\lceil r/\\log(1/δ)\\rceil)$ vertex-disjoint monochromatic cycles. We construct graphs that show this is tight up to the $(\\log r)$-factor…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-29","reactions":{}}