A note on the Alon-Saks-Seymour problem

Abstract

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\le 9$ by Gao et al., it was disproved by Huang and Sudakov, and further Balodis et al. proved that $f(k)\ge 2^{\tilde{\hat{I}}\text{c◯}((\log k{)}^2)}$. In this note, we give a simple proof of the recursive upper bound $f(k+1)\le f(k)+f(\lfloor k/4\rfloor )$. Consequently, $f(k)\le 2^{({\log }_2(4k){)}^2/4}$ for $k\ge 1$. This improves the previous best known upper bound of Mubayi and Vishwanathan in the exponent by a factor which is asymptotically two. Note that these bounds are sharp up to a lower order factor in the exponent by the result of Balodis et al.

2 pages