On the circumference of essentially 4-connected planar graphs

Publikationstyp
Journal Article
Date Issued
2020-01
Sprache
English
Author(s)
Fabrici, Igor  
Harant, Jochen  
Mohr, Samuel  
Schmidt, Jens M.  orcid-logo
TORE-URI
http://hdl.handle.net/11420/7600
Journal
Journal of graph algorithms and applications  
Volume
24
Issue
1
Start Page
21
End Page
46
Citation
Journal of Graph Algorithms and Applications (2020)
Publisher DOI
10.7155/jgaa.00516
Scopus ID
2-s2.0-85078255429
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