On the Circumference of Essentially 4-connected Planar Graphs

2018/06/25 by Fabrici, Igor, Harant, Jochen, Mohr, Samuel +1
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1806.09413

Abstract

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 (2n+4)/(5), 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 (5)/(8)(n+2). This improves the previously best-known lower bound (3)/(5)(n+2).

Related

• Circumference of essentially 4-connected planar triangulations
• Large cycles in essentially 4-connected graphs
• The Minimum Number of 4-Cycles in a Maximal Planar Graph with Small Number of Vertices
• Long cycles and spectral radii in planar graphs
• On the circumference, connectivity and dominating cycles