Long induced paths in minor-closed graph classes and beyond (Q2684889)

Summary: In this paper we show that every graph of pathwidth less than \(k\) that has a path of order \(n\) also has an induced path of order at least \(\frac{1}{3} n^{1/k}\). This is an exponential improvement and a generalization of the polylogarithmic bounds obtained by \textit{L. Esperet} et al. [Eur. J. Comb. 62, 1--14 (2017; Zbl 1358.05148)] for interval graphs of bounded clique number. We complement this result with an upper-bound. This result is then used to prove the two following generalizations: \begin{itemize} \item every graph of treewidth less than \(k\) that has a path of order \(n\) contains an induced path of order at least \(\frac{1}{4} (\log n)^{1/k}\); \item for every non-trivial graph class that is closed under topological minors there is a constant \(d \in (0,1)\) such that every graph from this class that has a path of order \(n\) contains an induced path of order at least \((\log n)^d\). \end{itemize} We also describe consequences of these results beyond graph classes that are closed under topological minors.