Monochromatic cycle partitions of $r$-edge-coloured graphs with high minimum degree
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.22117
curl -X POST /api/v1/records/arxiv/2601.22117/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.22117/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'