2025/07/08 by Alexey Pokrovskiy, Pokrovskiy, Alexey
Computer Science · Mathematics · #05D15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #G.2.2 #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2507.05842
openalex publication_date 2025/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Ryser conjectured that every r-edge-coloured complete graph can be covered by r-1 monochromatic trees. Motivated by a question of Austin in analysis, Milićević predicted something stronger -- that every r-edge-coloured complete graph can be covered by r-1 monochromatic trees of bounded diameter. Here we show that the two conjectures are equivalent. As immediate corollaries we obtain new results about Milićević's Conjecture, most notably that it is true for r=5. We also obtain several new cases of a generalization of Milićević's Conjecture to non-complete graphs due to DeBiasio-Kamel-McCourt-Sheats.