Tight cycle-partition conjecture for dense edge-coloured graphs

From papers

For r2r\geq2 and δ(0,1/2)\delta\in(0,1/2), let

cpr(δ):=lim supnmaxGG(n,r,δ)cp(G),cp_r(\delta):=\limsup_{n\to\infty}\max_{G\in\mathcal{G}(n,r,\delta)}cp(G),

where G(n,r,δ)\mathcal{G}(n,r,\delta) consists of the nn-vertex rr-edge-coloured graphs with δ(G)(1δ)n\delta(G)\geq(1-\delta)n, and cp(G)cp(G) is the smallest number of vertex-disjoint monochromatic cycles partitioning V(G)V(G). Tight cycle-partition conjecture. There exists K>0K>0 such that, for all r2r\geq2 and δ(0,1/2)\delta\in(0,1/2),

cpr(δ)Krrlog(1/δ).cp_r(\delta)\leq Kr\left\lceil\frac{r}{\log(1/\delta)}\right\rceil.

The conjecture would improve the paper's O(rlogrr/log(1/δ))\mathcal{O}(r\log r\lceil r/\log(1/\delta)\rceil) upper bound to the matching order suggested by the lower bound. It is known for δ=Ω(1)\delta=\Omega(1), but remains open in general.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Francesco Di Braccio and Viresh Patel, “Monochromatic cycle partitions of r-edge-coloured graphs with high minimum degree”, arXiv:2601.22117 (2026).

Additional references

3 papers in this index state this conjecture (2015–2026). The statement above is taken from the most recent of them; the others are arXiv:2008.00926, arXiv:1509.05539.

Solutions 0

No solutions have been posted yet.