- Series
- Graph Theory Working Seminar
- Time
- Thursday, January 30, 2020 - 4:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Michael Wigal – Georgia Tech
- Organizer
- 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.