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\'{ e}, Trotignon and Vu\v{ s}kovi\'{ c} (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).

Categories: math.CO

Bull-free graphs and $\chi$-boundedness