Tight tree-cover conjecture for dense edge-coloured graphs

From papers

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

tcr(δ):=lim supnmaxGG(n,r,δ)tc(G),tc_r(\delta):=\limsup_{n\to\infty}\max_{G\in\mathcal{G}(n,r,\delta)}tc(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 tc(G)tc(G) is the smallest number of not necessarily vertex-disjoint monochromatic trees covering V(G)V(G). Tight tree-cover conjecture. There exists K>0K>0 such that, for all r2r\geq2 and δ(0,1)\delta\in(0,1),

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

This is proposed as a stepping stone toward the corresponding cycle-partition conjecture. The source does not state a general resolution; it records stronger results in particular ranges, so the conjecture remains open.

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).

Solutions 0

No solutions have been posted yet.