The weakly sparse large-treewidth subclass meta-conjecture

About 1 year old · traced to

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 C′⊆C\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.