Please use this identifier to cite or link to this item:
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.
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) CC BY 4.0 (Attribution)
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
552.pdfVerlags-PDF348,82 kBAdobe PDFView/Open
Show full item record

Page view(s)

Last Week
Last month
checked on May 28, 2023


checked on May 28, 2023

Google ScholarTM


Note about this record

Cite this record


This item is licensed under a Creative Commons License Creative Commons