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

About 3 years old · traced to

Let k∈Nk\in\mathbb{N}, and let GG be a kk-degenerate graph with a path of order n≥1n\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 k∈Nk\in\mathbb{N} there is a constant c>0c>0 such that GG has an induced path of order at least

(log⁡n)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 log⁡log⁡n\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.

References

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.