Pathwidth–treedepth conjecture for graphs without long paths
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.
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
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.