Cocks's essential-family conjecture for unbounded treewidth
Cocks's essential-family conjecture for unbounded treewidth
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.
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.