The bounded-twin-width subclass conjecture for hereditary classes

From papers

A hereditary class is a graph class closed under induced subgraphs, and twin-width is the graph parameter measuring the minimum contraction complexity under sequences of vertex identifications. Bounded-twin-width conjecture. Every hereditary class of unbounded treewidth admits a subclass of unbounded treewidth and bounded twin-width. The paper notes that its constructions do not refute this conjecture, since bounded twin-width is not treewidth-hereditary; the conjecture remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Bogdan Alecu, Édouard Bonnet, Pedro Bureo Villafana and Nicolas Trotignon, “Every Graph is Essential to Large Treewidth”, arXiv:2502.14775 (2025).

Solutions 0

No solutions have been posted yet.