{"id":"arxiv/2605.03825","url":"https://arxiv.org/abs/2605.03825","tags":["math.CO"],"score":0,"title":"A generalization of Erdős-Hajnal problem on paths with equal-degree endpoints","domain":"math.CO","source":"arxiv","authors":["Xiamiao Zhao","Yichen Wang","Mei Lu"],"reviews":0,"subject":"math.CO","summary":"Erdős and Hajnal proposed a problem that: is it true that every $(2n+1)$-vertex graph with $n^2+n+1$ edges contains two vertices of equal degree connected by a path of length three? The edge bound is sharp by the complete bipartite graph $K_{n,n+1}$. Recently, Chen and Ma [Journal of Combinatorial Theory, Series B, 179:1-18, 2026] answered this problem affirmatively for every $n \\ge 600$. In the same paper, they further conjectured that for sufficiently large $n$, the statement is true if we replace the path of length three by a path of fixed odd length. In this paper, we confirm their…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-05","reactions":{}}