Pathwidth–treedepth conjecture for graphs without long paths

About 6 years old · traced to

Let GG be a graph, let pp be its pathwidth, and let ℓ\ell be a positive integer. A path of order 2ℓ2^\ell is a path with 2ℓ2^\ell vertices. Pathwidth–treedepth conjecture. Every graph with pathwidth pp that contains no path of order 2ℓ2^\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.

References

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.