Polynomial χ-boundedness for H-free forests

Informal conjecture (polynomial Gyárfás–Sumner) · arXiv:2202.09118

arXiv Informal medium confidence— first stated 2022-02-18

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

Status partial high confidence

The conjecture that every forest H is good (i.e., H-free graphs are polynomially χ-bounded) remains fully open for general H-free graph classes. Partial progress exists: companion paper arXiv:2202.10412 (same 2022 series) proves compositional closure results (H good implies H∪P₄ good), and arXiv:2407.16882 (2024) proves the polynomial Gyárfás–Sumner conjecture holds for the restricted class of intersection graphs of axis-aligned boxes in ℝ^d with no induced forest subgraph. The full statement for arbitrary H-free graphs is unresolved.

Cited literature (1)

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

Unknown (arXiv:2407.16882) · arXiv preprint · arXiv:2407.16882

Proves the polynomial Gyárfás–Sumner conjecture for intersection graphs of axis-aligned boxes in ℝ^d: for every forest F and positive integer d, such graphs with no induced F subgraph are polynomially χ-bounded.

Reviewer notes. The polynomial Gyárfás–Sumner conjecture is an active open problem. Known good forests (as of early 2026) include paths up to P₄, some trees, and their disjoint unions under certain conditions, but P₅ was still open at the time of the source paper. The 2024 result (arXiv:2407.16882) restricts to bounded-boxicity graphs, not general H-free graphs. Esperet's conjecture that every χ-bounded class is polynomially χ-bounded has been disproved, making the polynomial Gyárfás–Sumner conjecture even more specific and harder.

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

Informal. It might be true that every forest $H$ is good, i.e., the class of $H$-free graphs is polynomially $\chi$-bounded (strengthening the Gyárfás–Sumner conjecture from $\chi$-boundedness to polynomial $\chi$-boundedness).

Context

Say a forest $H$ is good if the class of $H$-free graphs is polynomially $\chi$-bounded. This has been proved only for a few simple kinds of tree and some of their disjoint unions; the polynomial strengthening of Gyárfás–Sumner is fully open.

Notes. Introduced with 'It might be true that'; no formal label.

Source paper

Polynomial bounds for chromatic number VII. Disjoint holes
Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl · 2022-02-18
https://arxiv.org/abs/2202.09118 PDF source