Circumference of essentially 4-connected planar triangulations
Vol. 25, no. 1, pp. 121-132, 2021. Regular paper.
Abstract A $3$-connected graph $G$ is essentially $4$-connected if, for any $3$-cut $S\subseteq 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 $\frac{2}{3}(n+4)$; moreover, this bound is sharp.

 This work is licensed under the terms of the CC-BY license.
Submitted: February 2020.
Reviewed: July 2020.
Revised: August 2020.
Accepted: January 2021.
Final: January 2021.
Published: January 2021.
Communicated by Giuseppe Liotta
article (PDF)