Path-partition height factor 2 tightness
Optimality of factor 2 in Lemma 4 · arXiv:1601.01886
Status open medium confidence
The open question asks whether the bound of $2k$ in Lemma 4 of arXiv:1601.01886 — every tree of pathwidth $k$ has a path-partition of height at most $2k$ — can be improved, i.e., whether the factor of 2 is necessary. No follow-up paper addressing the optimality of this factor was found in searches covering the period 2016–2026. Related work by overlapping authors (Joret, Micek et al.) on tight pathwidth bounds concerns different structural parameters (treedepth, treewidth) and does not resolve this specific question. The conjecture remains open with medium confidence given its age of roughly 9 years.
Reviewer notes. No follow-up paper resolving or improving the factor-2 bound in Lemma 4 was found after 5 web calls (2 WebSearch + 3 WebFetch). The survey on nonrepetitive graph colouring (Wood, arXiv:2009.02001) was identified as a potentially relevant source but its full content could not be verified within the call budget. The question is quite specific — it concerns the sharpness of a structural tool rather than the main theorem — and may have received little independent attention. Confidence is medium rather than high because the conjecture is ~9 years old.
Context
Lemma 4 is a key structural tool used in the proof of Theorem 2. The authors note that they made no effort to optimise the bound and leave open whether the factor 2 can be reduced.
Notes. Stated as 'we do not know whether the factor 2 is unavoidable' in prose immediately following the proof of Lemma 4; no labelled environment.
Source paper
Pathwidth and nonrepetitive list coloring
Adam Gągol, Gwenaël Joret, Jakub Kozik, Piotr Micek · 2016-10-02
https://arxiv.org/abs/1601.01886
PDF source