DeBiasio–Kamel–McCourt–Sheats bounded-diameter extension of Ryser's conjecture

Let α1\alpha\geq 1, let r2r\geq 2, and let GG be a graph with independence number α(G)=α\alpha(G)=\alpha. An rr-colouring of GG assigns one of rr colours to each edge, and a monochromatic component is a connected component in one colour class.

DeBiasio–Kamel–McCourt–Sheats conjecture. There exists a constant d=d(α)d=d(\alpha), depending only on α\alpha, such that every rr-colouring of GG has (r1)α(r-1)\alpha monochromatic components of diameter at most dd whose vertex sets cover GG.

This is a bounded-diameter extension of Ryser's conjecture from complete graphs to graphs with prescribed independence number. The source presents it as open; it would imply the corresponding bounded-diameter cover for every fixed independence number, uniformly in rr and in the graph.

Sources & referencesView supporting material

Primary source

Alexey Pokrovskiy, “Bounded diameter monochromatic component covers”, arXiv:2507.05842 (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.