Long induced paths in minor-closed graph classes and beyond
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.
- A Ramsey-type theorem for traceable graphs
- Graph minors. XVI: Excluding a non-planar graph
- Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation
- scientific article; zbMATH DE number 1696534 (Why is no real title available?)
- scientific article; zbMATH DE number 1375584 (Why is no real title available?)
- scientific article; zbMATH DE number 830463 (Why is no real title available?)
- Layered separators in minor-closed graph classes with applications
- Long cycles in 3-connected graphs
- Long induced paths in 3-connected planar graphs
- Long induced paths in graphs
- Lower and upper bounds for long induced paths in 3-connected planar graphs
- Sparsity. Graphs, structures, and algorithms
- Structure theorem and isomorphism test for graphs with excluded topological subgraphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Upper bounds to the clique width of graphs
- Excluding a long double path minor
- Estimating the number of graphs containing very long induced paths
- Some results on graphs without long induced paths
- Minor-Closed Graph Classes with Bounded Layered Pathwidth
- Long induced paths in graphs
- Induced subgraphs and path decompositions
- Sparse graphs without long induced paths
- Long induced paths in minor-closed graph classes and beyond
- Long induced paths and forbidden patterns: polylogarithmic bounds
- Graph theory. Abstracts from the workshop held January 5--10, 2025
- Treedepth and 2-treedepth in graphs with no long induced paths
This page was built for publication: Long induced paths in minor-closed graph classes and beyond
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2684889)
