Erdős–Faudree–Schelp–Simonovits conjecture on high-degree vertices and long paths

From papers

For positive integers n>dkn>d\geq k, let ϕ(n,d,k)\phi(n,d,k) be the smallest integer such that every nn-vertex graph with at least ϕ(n,d,k)\phi(n,d,k) vertices of degree at least dd contains a path Pk+1P_{k+1} on k+1k+1 vertices. Erdős–Faudree–Schelp–Simonovits conjecture. For any positive integers n>dkn>d\geq k,

ϕ(n,d,k)k12nd+1+ϵ,\phi(n,d,k)\leq \left\lfloor \frac{k-1}{2}\right\rfloor\left\lfloor\frac{n}{d+1}\right\rfloor+\epsilon,

where ϵ=1\epsilon=1 if kk is odd and ϵ=2\epsilon=2 otherwise. The conjecture gives the proposed sharp general upper bound for the minimum number of high-degree vertices forcing a path on k+1k+1 vertices; the paper presents a complete solution to this extremal problem, but the supplied material does not state whether this exact conjecture is resolved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Binlong Li, Jie Ma and Bo Ning, “Extremal problems of Erdős, Faudree, Schelp and Simonovits on paths and cycles”, arXiv:2102.04367 (2021).

Solutions 0

No solutions have been posted yet.