{"id":"arxiv/2605.28915","url":"https://arxiv.org/abs/2605.28915","tags":["math.CO","cs.DM"],"score":0,"title":"A note on the Alon-Saks-Seymour problem","domain":"math.CO","source":"arxiv","authors":["Jacob Fox"],"reviews":0,"subject":"math.CO","summary":"Let $f(k)$ be the maximum possible chromatic number of a graph whose edge set can be partitioned into at most $k$ complete bipartite graphs. Alon, Saks, and Seymour conjectured that $f(k)=k+1$ for all $k$. While the conjecture was verified for $k \\leq 9$ by Gao et al., it was disproved by Huang and Sudakov, and further Balodis et al. proved that $f(k) \\geq 2^{\\widetildeΩ((\\log k)^2)}$. In this note, we give a simple proof of the recursive upper bound $f(k+1) \\leq f(k)+f(\\lfloor k/4 \\rfloor)$. Consequently, $f(k) \\leq 2^{(\\log_2 (4k))^2/4}$ for $k \\geq 1$. This improves the previous best…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-27","reactions":{}}