Unavoidable induced subgraphs of large treewidth

Status disproved high confidence

What the 'disproved' badge means here: the question is not being declared meaningless or trivially closed — rather, the clean answer it hoped for is now proven impossible. Question 1.1 asks for the unavoidable induced subgraphs of graphs with large treewidth: the induced-subgraph analogue of the Robertson–Seymour Grid Minor theorem (where subdivided walls are the unavoidable subgraphs) and the central programmatic goal of the Chudnovsky–Hajebi–Spirkl 'Induced subgraphs and tree decompositions' series. The hope was a single 'holy grail' family F* of unavoidable induced subgraphs that works for every hereditary class of unbounded treewidth. That hope is refuted by Alecu, Bonnet, Bureo Villafana and Trotignon, 'Every Graph is Essential to Large Treewidth' (arXiv:2502.14775, Feb 2025): their Theorem 1.1 shows that for every single graph H there is a hereditary (weakly sparse) class of unbounded treewidth whose H-free subclass has bounded treewidth — so every graph H is 'essential', and no F* can work except the class of all graphs. There is therefore no clean induced analogue of the Grid Minor theorem, and several explicit conjectures fall with it (Hajebi's Conjectures 1.14/1.15 and a conjecture of Trotignon). What remains alive is the restricted programme: for specific excluded-obstruction classes the CHS series still proves treewidth characterizations (e.g. paper XIX, arXiv:2506.05602). So: general clean characterization — provably does not exist; structure theory for restricted hereditary classes — ongoing.

Cited literature (3)

• disproved 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

  Refutes the existence of an induced-subgraph analogue of the Grid Minor theorem. Theorem 1.1: for every graph H there is a hereditary weakly sparse class C_H of unbounded treewidth whose H-free subclass has bounded treewidth (strengthened in Thm 1.2 to: for every t, a class where H-free graphs of treewidth ≤ t have bounded treewidth, for every H). Consequence: no family F* of unavoidable induced subgraphs works except the class of all graphs — 'every graph is essential' — so Question 1.1 has no clean characterization in general. Built from a generalized 'abstract layered wheel' construction; also refutes Hajebi's Conjectures 1.14/1.15 and a conjecture of Trotignon.

• 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. Status changed open -> disproved on 2026-05-29 after arXiv:2502.14775 (Alecu, Bonnet, Bureo Villafana, Trotignon) was identified as refuting the strongest form of Question 1.1. The 'disproved' label refers to the implicit conjecture that a clean induced analogue of the Grid Minor theorem (a unavoidable-induced-subgraph family F*) exists; the broad question itself remains a live research programme for restricted classes, where characterizations are still being proved (CHS series papers XVI–XIX). Caveat: Question 1.1 is worded as an open-ended question rather than a yes/no conjecture, so 'disproved' is a curatorial judgement that the hoped-for clean characterization provably fails. Paper XVIII (arXiv:2412.17756, Dec 2024) fully resolves the analogous question for pathwidth. Earlier framing treated the question as fully open as of 2026.

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