{"id":"arxiv/2610.24484","url":"https://arxiv.org/abs/2610.24484","tags":["math.CO","cs.DM"],"score":0,"title":"Erdős-Gyárfás Balanced Five-Colorings","domain":"math.CO","source":"arxiv","authors":["Hai Xia","Stefan Szeider"],"reviews":0,"subject":"math.CO","summary":"A coloring of the edges of a complete graph with $r$ colors is balanced if the edges among any $r+1$ vertices use all $r$ colors. Erdős and Gyárfás (1999) conjectured that for all $r\\ge3$ the complete graph $K_{r^2+1}$ has no balanced $r$-coloring. They proved the conjecture for $r=3$ and $r=4$. We prove the conjecture for $r=5$, the first new case settled in over two decades. There is no balanced $5$-coloring of $K_{26}$, and since $K_{25}$ has one, $K_{25}$ is the largest complete graph admitting a balanced $5$-coloring. We design a reduce--dispatch--enumerate workflow, where every machine…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-17","reactions":{}}