Title: Finding long cycles in 3-connected graphs with bounded degrees


In 1993, Jackson and Wormald conjectured 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})$. In this talk we report

some recent progress on this problem. We

show that for $d\ge 50$, $G$ has a cycle of length $\Omega(
 n^{\log_{d} 2})$. 
Our proof uses Tutte decomposition of 2-connected

graphs into 3-connected components and some inequalities about convex

functions, and it implies an algorithm of complexity $O(n^2)$ which finds

a cycle of length at least $(1/2)n^{\log_{d} 2}+2$ for $d\ge 50$.


This is  based on the joint work with Guantao Chen, Xingxing Yu, and
Wenan Zang.