Bull-free graphs and $\chi$-boundedness

A bull is a graph obtained from a four-vertex path by adding a vertex adjacent to the two middle vertices of the path. A graph $G$ is bull-free if no induced subgraph of $G$ is a bull. We prove that for all $k,t\in \mathbb{N}$, if $G$ is a bull-free graph of clique number at most $k$ and every triangle-free induced subgraph of $G$ has chromatic number at most $t$, then $G$ has chromatic number at most $k^{\mathcal{O}(\log t)}$. We further show that the bound $k^{\mathcal{O}(\log t)}$ is best possible up to a multiplicative constant in the exponent. Thomassé, Trotignon and Vušković (2017) were the first to give a bound, of the form $2^{p\log p}$ where $p=\mathcal{O}(k^2+t)$, with a proof that uses Chudnovsky’s structure theorem for bull-free graphs. This was improved by Chudnovsky, Cook, Davies and Oum (2023) to a bound that is polynomial in $k$ (of degree linear in $t$), with a 10-page proof that again relies heavily on Chudnovsky’s structure theorem. Our proof is a single page long and completely avoids the structure theorem; instead using only one result of Chudnovsky and Safra (which itself has a short proof).