The bounded-twin-width subclass conjecture for hereditary classes
The bounded-twin-width subclass conjecture for hereditary classes
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
Sign in to submit a solution.
No solutions have been posted yet.