Esperet's polylogarithmic induced-path conjecture for k-degenerate graphs

Let kk be a positive integer. A graph is kk-degenerate if every subgraph has a vertex of degree at most kk. For a graph with a path of order nn, consider the order of its longest induced path.

Esperet's conjecture. There is a constant dd such that every kk-degenerate graph that has a path of order nn also has an induced path of order at least

(logn)d.(\log n)^d.

This conjecture asks whether the polylogarithmic lower bound is the correct general bound for induced paths in kk-degenerate graphs. It is posed as an open problem in the source; the paper proves such a bound for broader structural classes, but not for all kk-degenerate graphs.

Sources & referencesView supporting material

Primary source

Claire Hilaire and Jean-Florent Raymond, “Long induced paths in minor-closed graph classes and beyond”, arXiv:2201.03880 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.