Sharp Same-Color Cycle Covers in Two-Colored Complete Graphs
We extend the conjecture of Erdős and Gyárfás on monochromatic path covers to the setting of monochromatic cycle covers. We prove that, for all $n$, every 2-edge-coloring of the complete graph on $n$ vertices contains a collection of at most $\lceil\sqrt{n}\rceil$ monochromatic cycles, all of the same color, that together cover all vertices. The order of the bound is best possible, and the ceiling is necessary for infinitely many $n$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.27331
curl -X POST /api/v1/records/arxiv/2608.27331/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.27331/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'