Options
Circumference of essentially 4-connected planar triangulations
Citation Link: https://doi.org/10.15480/882.3580
Publikationstyp
Journal Article
Date Issued
2021-01
Sprache
English
Institut
TORE-DOI
TORE-URI
Volume
25
Issue
1
Start Page
121
End Page
132
Citation
Journal of Graph Algorithms and Applications (2021)
Publisher DOI
Scopus ID
A 3-connected graph G is essentially 4-connected if, for any 3-cut S⊆V(G) of G, at most one component of G−S contains at least two vertices. We prove that every essentially 4-connected maximal planar graph G on n vertices contains a cycle of length at least 23(n+4); moreover, this bound is sharp.
Subjects
circumference
long cycle
triangulation
essentially 4-connected
planar graph 2010 MSC: 05C38, 05C10
DDC Class
510: Mathematik
Publication version
publishedVersion
Loading...
Name
552.pdf
Size
348.82 KB
Format
Adobe PDF