Tight tree-cover conjecture for dense edge-coloured graphs

Less than 1 year old · traced to

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

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

tcr(δ)≤Kr⌈rlog⁡(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.

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

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.