Long induced paths in graphs

Abstract

We prove that every 3-connected planar graph on $n$ vertices contains an induced path on $\Omega (\log n)$ vertices, which is best possible and improves the best known lower bound by a multiplicative factor of $\log \log n$. We deduce that any planar graph (or more generally, any graph embeddable on a fixed surface) with a path on $n$ vertices, also contains an induced path on $\Omega (\sqrt{\log n})$ vertices. We conjecture that for any $k$, there is a contant $c(k)$ such that any $k$-degenerate graph with a path on $n$ vertices also contains an induced path on $\Omega ((\log n{)}^{c(k)})$ vertices. We provide examples showing that this order of magnitude would be best possible (already for chordal graphs), and prove the conjecture in the case of interval graphs.

20 pages, 5 figures - revised version

Cited by in corpus (1)

• Long induced paths and forbidden patterns: Polylogarithmic bounds