The pathwidth–treewidth incomparability conjecture

For each positive integer nn, let n_n be the class of graphs of pathwidth at most nn, and let n_n be the class of graphs of treewidth at most nn. Two graph classes are non-comparable if neither FO-transduces the other. The pathwidth–treewidth incomparability conjecture.

PWn+1 and TWn are non-comparable.\mathcal{PW}_{n+1}\text{ and }\mathcal{TW}_n\text{ are non-comparable.}

The authors state that this would imply strictness of the treewidth hierarchy, analogous to their proved strictness result for pathwidth. The supplied text does not establish a resolution.

Sources & referencesView supporting material

Primary source

Jaroslav Nesetril, Patrice Ossona de Mendez and Sebastian Siebertz, “Structural properties of the first-order transduction quasiorder”, arXiv:2010.02607 (2021).

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.