Esperet–Lemoine–Maffray conjecture on induced paths in degenerate graphs
Esperet–Lemoine–Maffray conjecture on induced paths in degenerate graphs
Let , and let be a -degenerate graph with a path of order . An induced path is a path whose vertices induce exactly the edges of the path in . Esperet–Lemoine–Maffray's conjecture. For every there is a constant such that has an induced path of order at least
This conjecture asks for a polylogarithmic lower bound on the order of an induced path in every bounded-degeneracy graph containing a path of order . The known general lower bound is of order , while planar graphs and more generally graphs of bounded Euler genus satisfy stronger polylogarithmic bounds; the conjecture remains open in the stated generality.
Sources & referencesView supporting material
Primary source
Oscar Defrain and Jean-Florent Raymond, “Sparse graphs without long induced paths”, arXiv:2304.09679 (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.