Extremal conjecture for equal-degree endpoint paths of odd length

About 1 year old · traced to

Let pℓ(N)p_{\ell}(N) denote the maximum number of edges in a graph on NN vertices containing no path of length ℓ\ell whose endpoints have equal degree. For odd integers ℓ≥3\ell\geq 3 and sufficiently large positive integers nn, consider graphs on 2n+12n+1 vertices; the complete bipartite graph Kn,n+1K_{n,n+1} has n2+nn^2+n edges.

Odd-length extremal conjecture. For any odd integer ℓ≥3\ell\geq 3 and sufficiently large nn, it holds that

pℓ(2n+1)=n2+n.p_{\ell}(2n+1)=n^2+n.

Equivalently, Kn,n+1K_{n,n+1} remains extremal for paths of every odd length at least three. This extends the problem of Erdős and Hajnal on paths with equal-degree endpoints; the asserted extremality is posed as an open problem for general odd lengths.

References

Primary source

Kaizhe Chen and Jie Ma, “A problem of Erdős and Hajnal on paths with equal-degree endpoints”, arXiv:2503.19569 (2025).

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.