Cocks's hereditary treewidth–clique boundedness conjecture

Let G\mathcal{G} be a hereditary graph class. A graph HH is HH-free in G\mathcal{G} when graphs in the relevant subclass have no induced subgraph isomorphic to HH. The class G\mathcal{G} is (tw,ω)(\operatorname{tw},\omega)-bounded if there is a function of clique number that bounds treewidth throughout G\mathcal{G}. Cocks's conjecture. The class G\mathcal{G} is (tw,ω)(\operatorname{tw},\omega)-bounded if and only if G\mathcal{G} excludes a complete bipartite graph and, for every non-complete graph HGH\in\mathcal{G}, the class of all HH-free graphs in G\mathcal{G} is (tw,ω)(\operatorname{tw},\omega)-bounded. The source identifies this conjecture as still open and says that its pathwidth analogue follows from the paper's main theorem.

Sources & referencesView supporting material

Primary source

Sepehr Hajebi, “Polynomial bounds for pathwidth”, arXiv:2510.19120 (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.