← All problems

Extremal conjecture for equal-degree endpoint paths of odd length

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
  1. 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.