Long induced paths in minor-closed graph classes and beyond (Q2684889)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Long induced paths in minor-closed graph classes and beyond |
scientific article |
Statements
Long induced paths in minor-closed graph classes and beyond (English)
0 references
17 February 2023
0 references
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.
0 references
maximum lengths of paths
0 references
induced paths
0 references
0 references