Large cycles in essentially 4-connected planar graphs

Graph Theory Working Seminar
Thursday, January 30, 2020 - 4:00pm for 1 hour (actually 50 minutes)
Skiles 006
Michael Wigal – Georgia Tech
Xingxing Yu

Tutte proved that every 4-connected planar graph contains a Hamilton cycle, but
there are 3-connected $n$-vertex graphs whose longest cycles have length
$\Theta(n^{\log_32})$. On the other hand,  Jackson and Wormald proved that an
essentially 4-connected $n$-vertex planar graph contains a cycle of
length at least $(2n+4)/5$, which was improved to $5(n+2)/8$ by Fabrici {\it et al}.  We improve this bound to $\lceil (2n+6)/3\rceil$ for $n\ge 6$ by proving a quantitative version of a result of Thomassen,
 and the bound is best possible.