Esperet's polylogarithmic induced-path conjecture for k-degenerate graphs
Esperet's polylogarithmic induced-path conjecture for k-degenerate graphs
Let be a positive integer. A graph is -degenerate if every subgraph has a vertex of degree at most . For a graph with a path of order , consider the order of its longest induced path.
Esperet's conjecture. There is a constant such that every -degenerate graph that has a path of order also has an induced path of order at least
This conjecture asks whether the polylogarithmic lower bound is the correct general bound for induced paths in -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 -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.