Polynomial χ-boundedness for forest-free graphs

Conjecture 1.3 · arXiv:2202.05557

arXiv Conjecture high confidence— first stated 2023-01-10

Status partial high confidence

Conjecture 1.3 — polynomial chi-boundedness for every forest-free graph class — remains open in full generality as of May 2026. Significant partial progress has been made: Nguyen (arXiv:2512.24907, 2025) proved the conjecture for H = P_5, the five-vertex path, resolving a case open since 1985; Davies and Yuditsky (arXiv:2407.16882, 2024) proved it for all forests H when the host graphs have bounded boxicity. The ongoing Scott–Seymour series establishes polynomial bounds for several additional tree families, but no uniform proof for all forests exists.

Cited literature (2)

partial Polynomial χ-boundedness for excluding P₅ (2025)

Tung H. Nguyen · arXiv preprint · arXiv:2512.24907

Proves that every P₅-free graph G satisfies χ(G) ≤ f(ω(G)) for a polynomial f, establishing Conjecture 1.3 for the specific forest H = P₅ (the five-vertex path).
partial Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity (2024)

James Davies, Yelena Yuditsky · arXiv preprint · arXiv:2407.16882

Proves Conjecture 1.3 for every forest H when restricted to intersection graphs of axis-aligned boxes in ℝ^d (graphs of bounded boxicity).

Reviewer notes. Conjecture 1.3 is closely related to Esperet's conjecture (polynomial chi-boundedness for hereditary classes, now disproved in general) and to the Gyárfás-Sumner conjecture (which concerns bounded chromatic number, not polynomial bounds). The P5 case (arXiv:2512.24907) and the bounded-boxicity case (arXiv:2407.16882) are the most notable post-2023 advances. Internal reference 2508.14332 appears unrelated.

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

Conjecture. For every forest $H$, there is a polynomial $f$ such that $\chi(G) \leq f(\omega(G))$ for every $H$-free graph $G$.

Context

This conjecture is presented as what the Gyárfás-Sumner conjecture (1.1) and Esperet's conjecture (that every $\chi$-bounded hereditary class has a polynomial bounding function) would jointly imply for forest-free graph classes. Esperet's conjecture has been disproved in full generality but remains open for classes excluding a forest, and Conjecture 1.3 is known only for a few special families of trees.

Notes. Stated in the paper without a parenthesised attribution; it is a natural combination of Conjecture 1.1 and Esperet's conjecture restricted to forest-free classes.

Source paper

Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph
Alex Scott, Paul Seymour · 2023-01-10
https://arxiv.org/abs/2202.05557 PDF source