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

Basile Couëtoux, Oscar Defrain, Jean-Florent Raymond

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 $\Omega (\log \log n)$. In this paper we…