Sharpness of treedepth O(thb) bound
Open Problem: sharpness of the treedepth bound in Theorem 1 · arXiv:2302.02995
Status open high confidence
The paper establishes that every graph of treewidth less than $t$ with no complete binary tree of height $h$ as a minor and no $2^b$-vertex path has treedepth $O(thb)$ (Theorem 1), while the constituent sub-bounds (Theorems 2 and 3) are each individually sharp up to constant factors. Whether the combined bound $O(thb)$ is optimal or can be reduced remains open. No follow-up work resolving this problem was found in a web search covering arXiv and journal literature through May 2026.
Reviewer notes. The individual bounds O(th) (treewidth × binary-tree height → pathwidth) and O(pathwidth × longest-path exponent) are each known to be sharp. The open question is whether the product structure in the combined bound O(thb) can be broken — e.g. whether O(th + hb + tb) or some sub-product suffices. No counterexample or improvement was found in the literature as of this review date. The paper was published in Combinatorica 44, 417–427 (2024).
Context
Theorems 2 and 3 together imply Theorem 1, and their individual bounds are each sharp up to constant factors. However, it is unknown whether the combined bound $O(thb)$ in Theorem 1 is optimal or can be reduced.
Notes. Stated as prose without a labelled theorem environment. PDF source — exponent notation inferred from context.
Source paper
Tight bound on treedepth in terms of pathwidth and longest path
Meike Hatzel, Gwenaël Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak · 2023-11-06
https://arxiv.org/abs/2302.02995
PDF source