Cocks's essential-family conjecture for unbounded treewidth

About 1 year old · traced to

A family of unbounded treewidth is a family of graphs whose treewidth is unbounded, and it is essential when its hereditary closure is a minimal hereditary class of unbounded treewidth. Cocks's conjecture. A family of unbounded treewidth is essential if and only if it contains only complete graphs, or only complete bipartite graphs. The source describes this as an open question concerning the characterization of essential families; the unresolved cases are narrowed to weakly sparse families.

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.