Polynomial χ-bounding in Gyárfás-Sumner

Status partial high confidence

The conjecture that the Gyárfás-Sumner conjecture holds with polynomial χ-bounding functions (chromatic number bounded by a polynomial in the clique number t) remains open in full generality. Significant partial progress has been made since 2023: polynomial χ-boundedness was established for P₅-free graphs (arXiv:2512.24907, Dec 2024), and the polynomial version of the conjecture was proved for intersection graphs of axis-aligned boxes of any fixed dimension (arXiv:2407.16882, Jul 2024). A further 2025 preprint (arXiv:2504.21127) improves bounds for P₅-free graphs and gives compositional results, but the full polynomial conjecture for all trees is still open.

Cited literature (3)

• partial Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity (2024)
  not confirmed in fetch · arXiv preprint · arXiv:2407.16882

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

• partial Polynomial χ-boundedness for excluding P₅ (2024)
  not confirmed in fetch · arXiv preprint · arXiv:2512.24907

  Proves that the chromatic number is polynomially bounded by the clique number for graphs with no induced five-vertex path P₅, resolving this case of the polynomial Gyárfás-Sumner conjecture via a chromatic density framework.

• partial On polynomially high-chromatic pure pairs (2025)
  Tung H. Nguyen · arXiv preprint · arXiv:2504.21127

  Improves the best known bound for P₅-free graphs from χ(G) ≤ ω^(log ω) to χ(G) ≤ ω^(O(log ω / log log ω)), and establishes that if T and a broom each satisfy the polynomial Gyárfás-Sumner conjecture then so does their disjoint union.

Reviewer notes. Esperet's broader conjecture that every χ-bounded hereditary class is polynomially χ-bounded was disproved by Briański, Davies and Walczak, but that does not affect this specific conjecture about forest-free graphs. The most notable advance is arXiv:2512.24907 (Dec 2024) proving polynomial χ-boundedness for P₅-free graphs. Author names for arXiv:2407.16882 and arXiv:2512.24907 were not returned by WebFetch and are marked accordingly.

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