Unavoidable induced subgraphs of large treewidth

Status disproved high confidence

A theorem of Alecu, Bonnet, Bureo Villafana, and Trotignon implies that every proper hereditary candidate obstruction family fails, so the only universal hereditary core is the tautological class of all graphs.

Cited literature (3)

• counterexample Every Graph is Essential to Large Treewidth (2025)
  Bogdan Alecu, Édouard Bonnet, Pedro Bureo Villafana, Nicolas Trotignon · arXiv preprint (v3, 1 Apr 2025) · arXiv:2502.14775

  A theorem of Alecu, Bonnet, Bureo Villafana, and Trotignon implies that every proper hereditary candidate obstruction family fails, so the only universal hereditary core is the tautological class of all graphs.

  Read the literature-status audit

• partial Induced subgraphs and tree decompositions XIX. Thetas and forests (2025)
  Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl · arXiv preprint · arXiv:2506.05602

  Proves treewidth is polynomially bounded by clique number in hereditary classes that are theta-free and exclude line graphs of subdivisions of some wall, making partial progress toward the full characterization sought by Question 1.1.

• partial A simple layered-wheel-like construction (2025)
  Authors unconfirmed from fetch · arXiv preprint · arXiv:2507.06169

  Constructs layered-wheel-like graphs achieving high girth with bounded outerstring treewidth, providing a simpler approach to the obstruction class identified as the last barrier to a complete induced-subgraph/treewidth characterization; also disproves a conjecture of Trotignon.

Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: Question 1.1 is open-ended; the negative resolution concerns the universal hereditary-core formulation, while restricted-class structure theory remains open.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.