Known forests for Esperet's polynomial χ-boundedness

Informal remark on completeness of known forests satisfying Esperet's conjecture · arXiv:2107.11780

arXiv Informal medium confidence— first stated 2021-07-25

Authors: Alex Scott, Paul Seymour, Sophie Spirkl

Status disproved high confidence

The remark in arXiv:2107.11780 that star-forests, double stars, K₂, and their induced subgraphs might constitute the complete list of forests H for which H-free graphs are polynomially χ-bounded is refuted: Nguyen (December 2025, arXiv:2512.24907) proved that P₅-free graphs are polynomially χ-bounded, and P₅ is a forest that is not an induced subgraph of any star, double star, or K₂. Separately, Briański–Davies–Walczak (2022, arXiv:2201.08814) disproved Esperet’s general conjecture by constructing hereditary χ-bounded classes that are not polynomially χ-bounded, confirming that polynomial χ-bounds are not automatic even within χ-bounded classes.

Cited literature (2)

counterexample Separating polynomial χ-boundedness from χ-boundedness (2022)

Marcin Briański, James Davies, Bartosz Walczak · Combinatorica · arXiv:2201.08814 · doi:10.1007/s00493-023-00054-3

Disproves Esperet’s general conjecture by constructing hereditary χ-bounded classes that are not polynomially χ-bounded, establishing that the question of which specific forests admit polynomial χ-bounds is non-trivial.
counterexample Polynomial χ-boundedness for excluding P₅ (2025)

Tung H. Nguyen · arXiv preprint · arXiv:2512.24907

Proves that P₅-free graphs are polynomially χ-bounded, exhibiting P₅ as a forest outside the class described in results 1.4–1.6 of arXiv:2107.11780 that satisfies the polynomial bound, directly disproving the completeness remark.

Reviewer notes. The authors themselves noted the completeness claim 'seems unlikely', and this is now confirmed: P₅ (a path on 5 vertices, not an induced subgraph of any star or double star) gives polynomial χ-bounds per Nguyen 2025. The general Esperet conjecture 1.2 was also independently disproved by Briański–Davies–Walczak (2201.08814). The class of forests admitting polynomial χ-bounds remains open but is strictly larger than what was known in 2021.

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

Informal. As far as we know (although it seems unlikely), [the forests described in results 1.4–1.6 and their induced subgraphs] might be all the forests that satisfy [Esperet's conjecture 1.2].

Context

After establishing their main results on star-forests and double stars, the authors pause to note the state of knowledge: the only forests known to satisfy Esperet's polynomial conjecture are those built from disjoint unions of stars, double stars, and $K_2$. They remark that these may be all such forests, though they consider this unlikely.

Notes. Authors signal explicit scepticism ('although it seems unlikely'), so this is a note on the limits of current knowledge rather than a firm conjecture.

Source paper

Polynomial bounds for chromatic number. II. Excluding a star-forest
Alex Scott, Paul Seymour, Sophie Spirkl · 2021-07-25
https://arxiv.org/abs/2107.11780 PDF source