The pathwidth–treewidth incomparability conjecture
The pathwidth–treewidth incomparability conjecture
For each positive integer , let be the class of graphs of pathwidth at most , and let be the class of graphs of treewidth at most . Two graph classes are non-comparable if neither FO-transduces the other. The pathwidth–treewidth incomparability conjecture.
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
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.