Milićević's bounded-diameter conjecture for monochromatic component covers

About 6 years old · traced to

Let rr be a positive integer. An rr-edge-coloured complete graph is a complete graph whose edges receive one of rr colours, and the diameter of a component is measured in its monochromatic subgraph.

Milićević's conjecture. For every rr, there is a constant D(r)D(r) such that every rr-edge-coloured complete graph can be covered by r−1r-1 monochromatic components of diameter at most D(r)D(r).

This strengthens the complete-graph case of Ryser's conjecture. The source reports that it is proved for r≤4r\leq 4, with bounds D(3)≤4D(3)\leq 4 and D(4)≤6D(4)\leq 6, while the general case remains open.

References

Primary source

Alexey Pokrovskiy, “Bounded diameter monochromatic component covers”, arXiv:2507.05842 (2026).

Additional references

2 papers in this index state this conjecture (2020–2025). The statement above is taken from the most recent of them; the others are arXiv:2009.07239.

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.