χ-bounded hereditary class without polynomial bound

Status solved high confidence

Briański, Davies, and Walczak (2022) answered the open problem affirmatively: they construct hereditary graph classes that are χ-bounded but not polynomially χ-bounded, published in Combinatorica. This resolves the question posed by Bonamy and Pilipczuk and refutes the hope (attributed to Esperet) that every χ-bounded hereditary class admits a polynomial bounding function. Follow-up work by Chudnovsky, Cook, Davies, and Oum (arXiv:2310.11167) introduced the ‘Pollyanna’ framework to study which graph classes preserve polynomial χ-boundedness when intersected with an arbitrary χ-bounded class.

Cited literature (2)

• proof Separating polynomial χ-boundedness from χ-boundedness (2022)
  Marcin Briański, James Davies, Bartosz Walczak · Combinatorica · arXiv:2201.08814 · doi:10.1007/s00493-023-00054-3

  Constructs, for every sufficiently fast-growing function f, a hereditary graph class where the maximum chromatic number of a graph with clique number n equals f(n), proving the existence of hereditary classes that are χ-bounded but not polynomially χ-bounded.

• survey Reuniting χ-boundedness with polynomial χ-boundedness (2023)
  Maria Chudnovsky, Linda Cook, James Davies, Sang-il Oum · arXiv preprint · arXiv:2310.11167

  Introduces the Pollyanna framework: a class ℱ is Pollyanna if ℱ ∩ ℳ is polynomially χ-bounded for every χ-bounded class ℳ, and establishes which structured graph classes satisfy this property in the wake of the Briański–Davies–Walczak separation.

Reviewer notes. The open problem asked for existence of a hereditary class that is χ-bounded but provably not polynomially χ-bounded. arXiv:2201.08814 (Combinatorica 2023) answers YES. The 2310.11167 entry is based on a WebFetch confirming the Chudnovsky–Cook–Davies–Oum authorship and Pollyanna framework; journal publication year may be 2026. No internal corpus references were supplied for this conjecture.

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