Sparse graphs without long induced paths

04/19/2023

∙

by   Oscar Defrain, et al.

∙

0

∙

share

Graphs of bounded degeneracy are known to contain induced paths of order Ω(loglog n) when they contain a path of order n, as proved by Nešetřil and Ossona de Mendez (2012). In 2016 Esperet, Lemoine, and Maffray conjectured that this bound could be improved to Ω((log n)^c) for some constant c>0 depending on the degeneracy. We disprove this conjecture by constructing, for arbitrarily large values of n, a graph that is 2-degenerate, has a path of order n, and where all induced paths have order O((loglog n)^2). We also show that the graphs we construct have linearly bounded coloring numbers.