Approximating Longest Cycles in Graphs with Bounded Degrees
Guantao Chen, Zhicheng Gao, Xingxing Yu, Wenan Zang · SIAM Journal on Computing · 2006
Jackson and Wormald conjecture that if G is a 3‐connected n‐vertex graph with maximum degree $d\ge 4$, then G has a cycle of length $\Omega(n^{\log_{d-1}2})$. We show that this conjecture holds when $d-1$ is replaced by $\max\{64,4d+1\}$. Our proof implies a cubic algorithm for finding such a cycle.