In 1982 Galvin, Rival, and Sands proved that in $K_{t,t}$-subgraph free graphs (t being fixed), the existence of a path of order n guarantees the existence of an induced path of order f(n), for some (slowly) increasing function f. The problem of obtaining good lower-bounds for f for specific graph classes was investigated decades later and logarithmic bounds have been obtained for planar graphs (more generally for graphs of bounded genus) and for interval graphs.
In this talk I will show that every graph of pathwidth less than k that has a path of order n also has an induced path of order $Ω(n^{1/k})$. I will then explain how this result can be 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 $Ω((\log n)^{1/k})$;
- for every non-trivial graph class that is closed under topological minors there is a constant d∈(0,1) such that every graph from this class that has a path of order n contains an induced path of order $Ω((\log n)^d)$.
Joint work with Claire Hilaire.