Monochromatic cycle partitions of $r$-edge-coloured graphs with high minimum degree
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908798648582144 |
|---|---|
| author | Di Braccio, Francesco Patel, Viresh |
| author_facet | Di Braccio, Francesco Patel, Viresh |
| contents | 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 for all values of $r$ and $δ$, and along the way disprove a conjecture of Bal and DeBiasio about monochromatic tree covering. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_22117 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Monochromatic cycle partitions of $r$-edge-coloured graphs with high minimum degree Di Braccio, Francesco Patel, Viresh Combinatorics 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 for all values of $r$ and $δ$, and along the way disprove a conjecture of Bal and DeBiasio about monochromatic tree covering. |
| title | Monochromatic cycle partitions of $r$-edge-coloured graphs with high minimum degree |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2601.22117 |