Polynomial χ-boundedness for H-free forest classes

Informal Conjecture (every forest is good) · arXiv:2202.10412

arXiv Informal medium confidence— first stated 2023-03-22

Authors: Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Status partial high confidence

The conjecture that every forest H is good (H-free graphs are polynomially χ-bounded) remains open in general, but has seen major progress. At the time of the source paper, P₅ was the smallest forest not known to be good; in December 2025 Tung H. Nguyen (arXiv:2512.24907) proved that P₅-free graphs are polynomially χ-bounded, resolving that open case. The polynomial Gyárfás-Sumner conjecture has also been established for bounded-boxicity graphs (arXiv:2407.16882). Forests requiring longer induced paths (P₆ and beyond) remain open.

Cited literature (3)

partial Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity (2024)

not retrieved · arXiv preprint · arXiv:2407.16882

Proves that for every positive integer d and every forest F, the class of intersection graphs of axis-aligned boxes in ℝ^d with no induced F is polynomially χ-bounded, establishing the polynomial Gyárfás-Sumner conjecture for bounded-boxicity graphs.
partial On polynomially high-chromatic pure pairs (2025)

Tung H. Nguyen · arXiv preprint · arXiv:2504.21127

Provides further supporting evidence for the polynomial Gyárfás-Sumner conjecture for P₅ by proving that every P₅-free graph with clique number ω≥2 contains a polynomially high-chromatic complete pair of induced subgraphs.
partial Polynomial χ-boundedness for excluding P₅ (2025)

Tung H. Nguyen · arXiv preprint · arXiv:2512.24907

Proves that chromatic number is polynomially bounded by clique number for graphs with no induced P₅, resolving the P₅ case of the conjecture and a 1985 open problem of Gyárfás; the full conjecture for all forests remains open.

Reviewer notes. The P₅ case (the smallest open case noted in the source paper) was resolved by Nguyen in December 2025 (arXiv:2512.24907). However, the full conjecture for every forest remains open: proving P₅-free is polynomially χ-bounded does not directly yield polynomial bounds for P₆-free or other larger-forest-free classes, since P₆-free is a strictly larger class. Authors for arXiv:2407.16882 were not extracted from the fetch.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. Perhaps every forest is good (i.e., for every forest $H$, the class of $H$-free graphs is polynomially $\chi$-bounded).

Context

After recalling that Esperet's conjecture that every $\chi$-bounded hereditary class is polynomially $\chi$-bounded was disproved, the authors ask which hereditary classes are polynomially $\chi$-bounded and raise in particular whether the Gyárfás-Sumner conjecture can be strengthened to polynomial $\chi$-boundedness. They note that among trees, only those not containing $P_5$ are currently known to be good, and that it is not even known whether $P_5$ is good.

Source paper

Polynomial bounds for chromatic number VI. Adding a four-vertex path
Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl · 2023-03-22
https://arxiv.org/abs/2202.10412 PDF source