On longest cycles in essentially 4-connected planar graphs
Igor Fabrici, Jochen Harant, Stanislav Jendrol′ · Discussiones Mathematicae Graph Theory · 2016
A planar 3-connected graph G is essentially 4-connected if, for any 3separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4connected planar graph on n vertices contains a cycle C such that |V (C)| 2n+4 5 . For a cubic essentially 4-connected planar graph G, Grnbaum with Malkevitch, and Zhang showed that G has a cycle on at least 3 4 n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover, new lower bounds on the length of a longest cycle of G are presented if G is an essentially 4-connected planar graph of maximum degree 4 or G is an essentially 4-connected maximal planar graph.