Hajebi's treewidth–clique boundedness conjecture
Hajebi's treewidth–clique boundedness conjecture
Let be a hereditary graph class. A graph is -degenerate if every induced subgraph has a vertex of degree at most , and is -bounded if there is a function of the clique number that bounds treewidth throughout . Hajebi's conjecture. The class is -bounded if and only if excludes a complete bipartite graph and every -degenerate graph in has bounded treewidth. The conjecture was disproved by Chudnovsky and Trotignon; the source notes that the corresponding pathwidth result is obtained as a consequence of its main theorem.
Sources & referencesView supporting material
Primary source
Sepehr Hajebi, “Polynomial bounds for pathwidth”, arXiv:2510.19120 (2025).
Additional references
2 papers in this index state this conjecture (2024–2025). The statement above is taken from the most recent of them; the others are arXiv:2405.07471.
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.