Note on induced paths in sparse random graphs

MaRDI QIDQ6360945zbMATH OpenFDO

Authors Stefan Glock

Publication date 18 February 2021

Abstract: We show that for $dge{d}_0(epsilon)$, with high probability, the random graph $G(n,d/n)$ contains an induced path of length $(3/2-epsilon)fracndlogd$. This improves a result obtained independently by Luczak and Suen in the early 90s, and answers a question of Fernandez de la Vega. Along the way, we generalize a recent result of Cooley, Dragani'c, Kang and Sudakov who studied the analogous problem for induced matchings.

This page was built for publication: Note on induced paths in sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6360945)