Bull-free graphs and $\ddot{I}‡$-boundedness

Abstract

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^{O(\log t)}$. We further show that the bound $k^{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=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 (2026) to a bound of the form $k^{O(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 a result of Chudnovsky and Safra (which itself has a short proof).