Esperet–Lemoine–Maffray conjecture on induced paths in degenerate graphs

Let kNk\in\mathbb{N}, and let GG be a kk-degenerate graph with a path of order n1n\geq 1. An induced path is a path whose vertices induce exactly the edges of the path in GG. Esperet–Lemoine–Maffray's conjecture. For every kNk\in\mathbb{N} there is a constant c>0c>0 such that GG has an induced path of order at least

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

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 nn. The known general lower bound is of order loglogn\log\log n, 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

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.