Tight cycle-partition conjecture for dense edge-coloured graphs

About 11 years old · traced to

For r≥2r\geq2 and δ∈(0,1/2)\delta\in(0,1/2), let

cpr(δ):=lim sup⁡n→∞max⁡G∈G(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 r≥2r\geq2 and δ∈(0,1/2)\delta\in(0,1/2),

cpr(δ)≤Kr⌈rlog⁡(1/δ)⌉.cp_r(\delta)\leq Kr\left\lceil\frac{r}{\log(1/\delta)}\right\rceil.

The conjecture would improve the paper's O(rlog⁡r⌈r/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.

References

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.

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.