The pathwidth–clique-number conjecture for bounded alpha-treewidth

From papers

Let G\mathcal{G} be a graph class. For graph parameters ρ\rho and ω\omega, say that G\mathcal{G} is (ρ,ω)(\rho,\omega)-bounded when bounded clique number in G\mathcal{G} implies bounded ρ\rho; write α\alpha-treewidth for the independence variant of treewidth. Pathwidth conjecture. Every (pw,ω)(\operatorname{pw},\omega)-bounded graph class has bounded α\alpha-treewidth.

This is one of two weaker statements left open after the construction of graph classes with clique-bounded treewidth and unbounded α\alpha-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

No solutions have been posted yet.