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 Esperet, Lemoine and Maffray (2016) 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: 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}$; 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$. We also describe consequences of these results beyond graph classes that are closed under topological minors.
@article{10_37236_11029,
author = {Claire Hilaire and Jean-Florent Raymond},
title = {Long induced paths in minor-closed graph classes and beyond},
journal = {The electronic journal of combinatorics},
year = {2023},
volume = {30},
number = {1},
doi = {10.37236/11029},
zbl = {1507.05053},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11029/}
}
TY - JOUR
AU - Claire Hilaire
AU - Jean-Florent Raymond
TI - Long induced paths in minor-closed graph classes and beyond
JO - The electronic journal of combinatorics
PY - 2023
VL - 30
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/11029/
DO - 10.37236/11029
ID - 10_37236_11029
ER -
%0 Journal Article
%A Claire Hilaire
%A Jean-Florent Raymond
%T Long induced paths in minor-closed graph classes and beyond
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/11029/
%R 10.37236/11029
%F 10_37236_11029
Claire Hilaire; Jean-Florent Raymond. Long induced paths in minor-closed graph classes and beyond. The electronic journal of combinatorics, Tome 30 (2023) no. 1. doi: 10.37236/11029
