Cocks's hereditary treewidth–clique boundedness conjecture
Cocks's hereditary treewidth–clique boundedness conjecture
Let be a hereditary graph class. A graph is -free in when graphs in the relevant subclass have no induced subgraph isomorphic to . The class is -bounded if there is a function of clique number that bounds treewidth throughout . Cocks's conjecture. The class is -bounded if and only if excludes a complete bipartite graph and, for every non-complete graph , the class of all -free graphs in is -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.