Erdős–Faudree–Schelp–Simonovits conjecture on high-degree vertices and long paths
Erdős–Faudree–Schelp–Simonovits conjecture on high-degree vertices and long paths
For positive integers , let be the smallest integer such that every -vertex graph with at least vertices of degree at least contains a path on vertices. Erdős–Faudree–Schelp–Simonovits conjecture. For any positive integers ,
where if is odd and otherwise. The conjecture gives the proposed sharp general upper bound for the minimum number of high-degree vertices forcing a path on 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
Sign in to submit a solution.
No solutions have been posted yet.