Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00552
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
|
Journal Supporters
|