Finding long cycles in 3-connected graphs with bounded degrees

computationally very dicult. The problem becomes easier for 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  4 then
G has a cycle of length nlogd􀀀1 2. In this talk we show that for d  50,
G has a cycle of length nlogd 2. Our proof uses Tutte decomposition of 2-
connected graphs into 3-connected components, and it implies an algorithm
of complexity O(n2) which nds a cycle of length at least (1=2)nlogd 2 + 2.
This is based on the joint work with Guantao Chen, Xingxing Yu, and
Wenan Zang.
1