Circumference of essentially 4-connected planar triangulations

Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.3580

Publisher DOI:	10.7155/jgaa.00552
Title:	Circumference of essentially 4-connected planar triangulations
Language:	English
Authors:	Fabrici, Igor Harant, Jochen Mohr, Samuel Schmidt, Jens M.
Keywords:	circumference; long cycle; triangulation; essentially 4-connected; planar graph 2010 MSC: 05C38, 05C10
Issue Date:	Jan-2021
Source:	Journal of Graph Algorithms and Applications (2021)
Abstract (english):	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.
URI:	http://hdl.handle.net/11420/8419
DOI:	10.15480/882.3580
ISSN:	1526-1719
Journal:	Journal of graph algorithms and applications
Institute:	Algorithmen und Komplexität E-11
Document Type:	Article
Project:	Probleme der Strukturellen und Chromatischen Graphentheorie
License:	CC BY 4.0 (Attribution)
Appears in Collections:	Publications with fulltext