Abstract:

In general finding a longest cycle in a graph is a very difficult problem. 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 at least $\Omega(n^r)$ with $r= \log 2/\log (d-1).$ In this talk we show how to find in such graphs a long cycle with $r=\log 2/\log (2d)$, when $d\ge 16$. Our argument also gives a long cycle with $r=\log 2/\log (d+\epsilon)$ for sufficiently large $d$. Previously known best value is $r=\log 2/\log (d^2-d+1)$. We also mention similar results about 3-connected planar graphs.