Polynomial χ-boundedness for forest-free graphs

Status partial high confidence

Conjecture 1.3 — that for every forest H there exists c > 0 such that every H-free graph G satisfies chi(G) <= omega(G)^c — remains open in full generality. It has been established for star-forests and double stars (Scott–Seymour–Spirkl), and a fractional-colouring version has been proved for all multibrooms by Nguyen–Scott–Seymour (2024). For trees of radius two a polynomial bound in tau_d(G) is known (Scott–Seymour 2023), which yields a doubly-exponential but not polynomial bound in omega(G). For P_5-free graphs the best known bound is chi(G) <= omega(G)^{log_2(omega(G))}, a near-polynomial result proved in the source paper itself.

Cited literature (2)

• partial Trees and near-linear stable sets (2024)
  Tung Nguyen, Alex Scott, Paul Seymour · arXiv preprint · arXiv:2409.09397

  Proves a fractional-colouring version of the polynomial chi-bound conjecture for all multibrooms H, and shows that every {H, K_{k+1}}-free graph G with H a forest satisfies alpha(G) >= |G|^{1-o(1)}, but does not prove the full chi(G) <= omega(G)^c for general forests.

• partial Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph (2023)
  Alex Scott, Paul Seymour · Journal of Combinatorial Theory, Series B · arXiv:2202.05557

  For every tree H of radius two and integer d >= 1 proves chi(G) <= f(tau_d(G)) polynomially for H-free graphs, yielding a doubly-exponential bound in omega(G) — partial progress toward a polynomial bound in omega(G) but with an additional multipartite-graph exclusion.

Reviewer notes. This conjecture is the polynomial strengthening of the Gyarfas-Sumner conjecture (sometimes linked to Esperet's general polynomial chi-boundedness conjecture). It is open for general forests; the source paper's own best result for P_5-free graphs is the near-polynomial bound omega^{log_2(omega)}. A survey paper arxiv:2512.09186 ('Towards Esperet's Conjecture', Dec 2025) addresses polynomial chi-bounds for structured classes including broom-free and C_4-free graphs, but does not appear to resolve the general forest case.

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