Characterisation of poly-χ-bounded hereditary classes

Status open high confidence

The overarching question of characterising which hereditary classes are polynomially χ-bounded remains open. After Briański, Davies and Walczak disproved Esperet's conjecture (that every χ-bounded hereditary class is poly-χ-bounded), the Pollyanna framework was introduced to organise which hereditary classes do satisfy a polynomial binding function, with specific forbidden-subgraph families now confirmed to be poly-χ-bounded. No complete characterisation is known as of 2026.

Cited literature (2)

• partial Polynomial bounds for chromatic number VI. Adding a four-vertex path (2022)
  Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl · arXiv preprint · arXiv:2202.10412

  Proves polynomial χ-boundedness for {H1, H2}-free graphs when every component of H1 is a good forest and H2 is a broom or P4, extending the catalogue of poly-χ-bounded hereditary classes.

• partial Pollyanna and Polynomially χ-Bounded Graph Classes (2026)
  Narjes Rahimi, D. A. Mojdeh · arXiv preprint · arXiv:2602.14542

  Proves three new strong Pollyanna results, including that for each t ≥ 2 the class of {diamond, hammer(t)⁺}-free graphs is t-strongly Pollyanna, advancing the programme of identifying which hereditary classes are poly-χ-bounded.

Reviewer notes. Esperet's conjecture (every χ-bounded hereditary class is poly-χ-bounded) was disproved by Briański, Davies and Walczak (arXiv:2201.08814, published Combinatorica 2024); this is the direct motivation for the question as stated in the source paper. The Pollyanna framework — asking which hereditary classes C have the property that C ∩ F is poly-χ-bounded for every χ-bounded F — has been developed as a structured approach to the overarching question. A related but distinct direction (arXiv:2512.09176, Rahimi and Mojdeh 2025) studies an analogue using the domination parameter τ_d(G) rather than ω(G). Internal reference arXiv:2311.05719 appears to be a treewidth paper mismatched to this conjecture identifier.

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