2025/04/29 by Hajebi, Sepehr
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2504.21093
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 kO(log t). We further show that the bound kO(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 2plog p where p=O(k2+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).