The pathwidth–clique-number conjecture for bounded alpha-treewidth
The pathwidth–clique-number conjecture for bounded alpha-treewidth
Let be a graph class. For graph parameters and , say that is -bounded when bounded clique number in implies bounded ; write -treewidth for the independence variant of treewidth. Pathwidth conjecture. Every -bounded graph class has bounded -treewidth.
This is one of two weaker statements left open after the construction of graph classes with clique-bounded treewidth and unbounded -treewidth; its status remains open.
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
Kenny Bešter Štorgel, Clément Dallard, Vadim Lozin, Martin Milanič and Viktor Zamaraev, “Awesome graph parameters”, arXiv:2511.05285 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.