Large cycles in essentially 4-connected graphs

Abstract

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

17 pages, 4 figures