DeBiasio–Kamel–McCourt–Sheats bounded-diameter extension of Ryser's conjecture
DeBiasio–Kamel–McCourt–Sheats bounded-diameter extension of Ryser's conjecture
Let , let , and let be a graph with independence number . An -colouring of assigns one of 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 , depending only on , such that every -colouring of has monochromatic components of diameter at most whose vertex sets cover .
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 and in the graph.
Sources & referencesView supporting material
Primary source
Alexey Pokrovskiy, “Bounded diameter monochromatic component covers”, arXiv:2507.05842 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.