Chen and Ma's conjecture on equal-degree endpoints joined by odd paths

Less than 1 year old · traced to

Let nn be a positive integer, and let ℓ≥2\ell\geq 2 be fixed. Consider graphs on 2n+12n+1 vertices, and say that two vertices are joined by a path of length 2ℓ+12\ell+1 when such a path has those vertices as its endpoints. Chen and Ma's conjecture. For sufficiently large nn, the maximum number of edges in a graph that does not contain two vertices of the same degree joined by a path of length 2ℓ+12\ell+1 is at most n2+nn^2+n.

The case of paths of length three was proved by Chen and Ma for n≥600n\geq 600, with the bound later improved to n≥2n\geq 2 by Liu and Zeng. The conjecture extends this extremal equal-degree-endpoint problem to every fixed odd path length; the source paper states that it confirms the conjecture.

References

Primary source

Xiamiao Zhao, Yichen Wang and Mei Lu, “A generalization of Erdős-Hajnal problem on paths with equal-degree endpoints”, arXiv:2605.03825 (2026).

Additional references

2 papers in this index state this conjecture (2026). The statement above is taken from the most recent of them; the others are arXiv:2604.11664.

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.