Bull-free graphs and χ -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 ∈ ℕ , 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).