Pathwidth–treedepth conjecture for graphs without long paths
Let be a graph, let be its pathwidth, and let be a positive integer. A path of order is a path with vertices. Pathwidth–treedepth conjecture. Every graph with pathwidth that contains no path of order has treedepth . 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
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.