Graphs with a forbidden induced tree are chi-bounded
Status partial high confidence
The Gyárfás–Sumner conjecture remains open in full generality for all trees. Significant recent progress includes Nguyen, Scott, and Seymour (2024) proving that every $H$-free graph (for any forest $H$) with bounded clique number has a stable set of size $|G|^{1-o(1)}$ (near-linear), and Davies and Yuditsky (2024) proving the polynomial version of the conjecture for intersection graphs of axis-aligned boxes (bounded boxicity).
Cited literature (4)
-
For every forest $H$, every $H$-free graph with bounded clique number has a stable set of size $|G|^{1-o(1)}$; moreover, multibrooms satisfy a fractional colouring version of the Gyárfás–Sumner conjecture.
-
For every positive integer $d$ and forest $F$, the class of intersection graphs of axis-aligned boxes in $\mathbb{R}^d$ with no induced $F$ subgraph is polynomially $\chi$-bounded.
-
partial Degeneracy of $P_t$-free and $C_{\geq t}$-free graphs with no large complete bipartite subgraphs (2021)
Proves a biclique-exclusion relaxation: every $C_{\geq t}$-free graph containing no $K_{\ell,\ell}$ as a subgraph satisfies $\chi(G) \leq \ell^{f(t)}+1$, giving a polynomial bound in $\ell$ under the additional assumption of no large balanced biclique.
-
Proves that if $H$ is a good forest then the disjoint union of $H$ and $P_4$ is also good (polynomially $\chi$-bounded), in particular showing that $2P_4$-free graphs satisfy $\chi(G) \leq \omega(G)^{16}$; more generally proves polynomial $\chi$-boundedness for $\{H_1, H_2\}$-free graphs when every component of $H_1$ is good and $H_2$ is a broom or disjoint union of a good forest and paths.
Reviewer notes. The Scott–Seymour long series on induced subgraphs of graphs with large chromatic number contains many partial results for specific tree families (paths, multibrooms, radius-2 trees), predating the 2024 results cited here. The full conjecture for all trees remains open. Published Springer links for the Combinatorica version of 2409.09397 redirected to a login page and could not be fetched directly.
Discussion
This deep conjecture remains open despite considerable effort. Note that the conjecture would be false were the graph $ T $ to be permitted to contain a cycle, since then the class would admit graphs of high girth (where $ \omega = 2 $ ) and high chromatic number. It is an easy exercise to prove this conjecture in the special case when $ T $ is either a path or a star, but things get difficult from here. Kierstead and Penrice solved the special case when $ T $ has radius 2, and Kierstead and Zhu solved the special case when $ T $ has radius 3 and has the property that every vertex incident with the center vertex has degree 2. Scott proved that the class of graphs which exclude all subdivisions of a fixed tree $ T $ as induced subgraphs are $ \chi $ -bounded. It follows from this that Gyarfas's conjecture also holds for subdivisions of stars.