Hamiltonicity, independence number, and pancyclicity

A graph on nn vertices is called pancyclic if it contains a cycle of length ℓℓ for all 3≤ℓ≤n3≤ℓ≤n. In 1972, Erdős proved that if GG is a Hamiltonian graph on n>4k4n>4k4 vertices with independence number kk, then GG is pancyclic. He then suggested that n=Ω(k2)n=Ω(k2) should already be enough to guarantee pancyclicity. Improving on his and some other later results, we prove that there exists a constant cc such that n>ck7/3n>ck7/3 suffices.

► We study a relation between pancyclicity, Hamiltonicity, and independence number. ► We make progress on an old conjecture of Erdős. ► Improve results of Keevash and Sudakov.