On the circumference of essentially 4-connected planar graphs

A planar graph is essentially 4-connected if it is 3-connected and every of its 3-separators is the neighborhood of a single vertex. Jackson and Wormald proved that every essentially 4-connected planar graph G on n vertices contains a cycle of length at least (Formula presented), and this result has recently been improved multiple times. In this paper, we prove that every essentially 4-connected planar graph G on n vertices contains a cycle of length at least (Formula presented) (n+2). This improves the previously best-known lower bound (Formula presented) (n+2).

DDC Class

510: Mathematik

Options

On the circumference of essentially 4-connected planar graphs