The weakly sparse large-treewidth subclass meta-conjecture

From papers

Let Π\Pi be a graph-class property. A hereditary weakly sparse class is a hereditary graph class excluding some biclique Kt,tK_{t,t} as a subgraph. Meta-conjecture-ws(Π)(\Pi). Every hereditary weakly sparse class C\mathcal C of unbounded treewidth contains a subclass CC\mathcal C'\subseteq\mathcal C of unbounded treewidth with property Π\Pi. The paper refutes this for every finitely-hereditary or treewidth-hereditary property Π\Pi, while properties such as bounded twin-width are not refuted by the construction.

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.