Bal–DeBiasio conjecture on monochromatic tree covers

About 9 years old · traced to

Let GG be an nn-vertex rr-edge-coloured graph, and let tc(G)tc(G) be the smallest number of not necessarily vertex-disjoint monochromatic trees whose vertices cover V(G)V(G). Bal–DeBiasio conjecture. For every r≥2r\geq2, if

δ(G)≥r(n−r+1)+1r+1,\delta(G)\geq\frac{r(n-r+1)+1}{r+1},

then tc(G)≤rtc(G)\leq r. The conjecture was settled affirmatively by Bucić, Korándi, and Sudakov, so it is solved.

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 (2017–2026). The statement above is taken from the most recent of them; the others are arXiv:2403.12587, arXiv:1708.01284.

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.