Pathwidth–treedepth conjecture for graphs without long paths

Let GG be a graph, let pp be its pathwidth, and let \ell be a positive integer. A path of order 22^\ell is a path with 22^\ell vertices. Pathwidth–treedepth conjecture. Every graph with pathwidth pp that contains no path of order 22^\ell has treedepth O(p)O(p\ell). This would sharpen the known bound for treedepth in terms of treewidth, the height of a forbidden complete-binary-tree subdivision, and the length of a forbidden path; the source presents it as an open conjecture and gives no resolution.

Sources & referencesView supporting material

Primary source

Carla Groenland, Gwenaël Joret, Wojciech Nadara and Bartosz Walczak, “Approximating pathwidth for graphs of small treewidth”, arXiv:2008.00779 (2022).

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.