A quasi-optimal upper bound for induced paths in sparse graphs

Abstract

In 2012, NeÅ¡etřil and Ossona de Mendez proved that graphs of bounded degeneracy that have a path of order $n$ also have an induced path of order $\hat{I}\text{c◯}(\log \log n)$. In this paper we give an almost matching upper bound by describing, for arbitrarily large values of $n$, 2-degenerate graphs that have a path of order $n$ and where the longest induced paths have order $O((\log \log n{)}^{1+o(1)})$.

37 pages, 13 figures, updated introduction