Bull-free graphs and $\chi $-boundedness
Hajebi, Sepehr1
1Department of Combinatorics and Optimization, University of Waterloo
Innovations in Graph Theory, Volume 3 (2026), pp. 247-253

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).

Received:
Accepted:
Published online:
DOI: 10.5802/igt.23
Classification: 05C15, 05C75
Keywords: Graph coloring, Chi-boundedness, Induced subgraphs, Bull-free graphs

Hajebi, Sepehr  1

1 Department of Combinatorics and Optimization, University of Waterloo
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
Hajebi, Sepehr. Bull-free graphs and $\chi $-boundedness. Innovations in Graph Theory, Volume 3 (2026), pp. 247-253. doi: 10.5802/igt.23
@article{IGT_2026__3__247_0,
     author = {Hajebi, Sepehr},
     title = {Bull-free graphs and $\chi $-boundedness},
     journal = {Innovations in Graph Theory},
     pages = {247--253},
     year = {2026},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {3},
     doi = {10.5802/igt.23},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.23/}
}
TY  - JOUR
AU  - Hajebi, Sepehr
TI  - Bull-free graphs and $\chi $-boundedness
JO  - Innovations in Graph Theory
PY  - 2026
SP  - 247
EP  - 253
VL  - 3
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.23/
DO  - 10.5802/igt.23
LA  - en
ID  - IGT_2026__3__247_0
ER  - 
%0 Journal Article
%A Hajebi, Sepehr
%T Bull-free graphs and $\chi $-boundedness
%J Innovations in Graph Theory
%D 2026
%P 247-253
%V 3
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.23/
%R 10.5802/igt.23
%G en
%F IGT_2026__3__247_0

[1] Bourneuf, Romain; Thomassé, Stéphan Bounded twin-width graphs are polynomially $\chi $-bounded, Adv. Comb. (2025), Paper no. 2, 19 pages | DOI | MR | Zbl

[2] Briański, Marcin; Davies, James; Walczak, Bartosz Separating polynomial $\chi $-boundedness from $\chi $-boundedness, Combinatorica, Volume 44 (2024) no. 1, pp. 1-8 | DOI | MR | Zbl

[3] Carbonero, Alvaro; Hompe, Patrick; Moore, Benjamin; Spirkl, Sophie A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number, J. Comb. Theory, Ser. B, Volume 158 (2023), pp. 63-69 | DOI | MR | Zbl

[4] Chudnovsky, Maria The structure of bull-free graphs I—Three-edge-paths with centers and anticenters, J. Comb. Theory, Ser. B, Volume 102 (2012) no. 1, pp. 233-251 | DOI | MR | Zbl

[5] Chudnovsky, Maria The structure of bull-free graphs II–Elementary trigraphs, 2012 (Available online in the Supplementary material of [7])

[6] Chudnovsky, Maria The structure of bull-free graphs III–Global structure, 2012 (Available online in the Supplementary material of [7])

[7] Chudnovsky, Maria The structure of bull-free graphs II and III—A summary, J. Comb. Theory, Ser. B, Volume 102 (2012) no. 1, pp. 252-282 | DOI | MR | Zbl

[8] Chudnovsky, Maria; Cook, Linda; Davies, James; Oum, Sang-il Reuniting $\chi $-boundedness with polynomial $\chi $-boundedness, J. Comb. Theory, Ser. B, Volume 176 (2026), pp. 30-73 | DOI | MR | Zbl

[9] Chudnovsky, Maria; Penev, Irena; Scott, Alex; Trotignon, Nicolas Substitution and $\chi $-boundedness, J. Comb. Theory, Ser. B, Volume 103 (2013) no. 5, pp. 567-586 | DOI | MR | Zbl

[10] Chudnovsky, Maria; Safra, Shmuel The Erdős–Hajnal conjecture for bull-free graphs, J. Comb. Theory, Ser. B, Volume 98 (2008) no. 6, pp. 1301-1310 | DOI | MR | Zbl

[11] Esperet, Louis Graph colorings, flows and perfect matchings, 2017 (habilitation thesis, Univ. Grenoble Alpes)

[12] Larsen, Michael; Propp, James; Ullman, Daniel The fractional chromatic number of Mycielski’s graphs, J. Graph Theory, Volume 19 (1995) no. 3, pp. 411-416 | DOI | MR | Zbl

[13] Mycielski, Jan Sur le coloriage des graphs, Colloq. Math., Volume 3 (1955), pp. 161-162 | DOI | MR | Zbl

[14] Nešetřil, Jaroslav Teorie grafů, Vyd. 1. Praha: Státní Nakladatelství Technické Literatury (1979)

[15] Scott, Alex Graphs of large chromatic number, ICM—International Congress of Mathematicians. Vol. 6. Sections 12–14, EMS, 2023, pp. 4660-4680 | MR | Zbl | DOI

[16] Scott, Alex; Seymour, Paul A survey of $\chi $-boundedness, J. Graph Theory, Volume 95 (2020) no. 3, pp. 473-504 | DOI | MR | Zbl

[17] Thomassé, Stéphan; Trotignon, Nicolas; Vušković, Kristina A polynomial Turing-kernel for weighted independent set in bull-free graphs, Algorithmica, Volume 77 (2017) no. 3, pp. 619-641 | DOI | MR | Zbl

Cited by Sources: