Long cycles in graphs on a fixed surface
type: Item
instance of: scholarly article
title: Long cycles in graphs on a fixed surface
zbMATH Open document ID: 1025.05035
author: T. Böhme
author: Bojan Mohar
author: Carsten Thomassen
published in: Journal of Combinatorial Theory. Series B
publication date: 2002-12-10T00:00:00Z
review text: The authors' main result states, for fixed \(g\) and \(\varepsilon\), that if \(G\) is a 4-connected graph with \(n\) vertices that has an embedding of Euler genus \(g\) and whose shortest non-contractible cycle is sufficiently large, then the vertices of \(G\) can be covered by two cycles each of which has length at least \((1 -\varepsilon)n\). From this they deduce, among other things, the existence of functions \(b(g)\) and \(c(g)\) such that if \(G\) is a graph with \(n\) vertices that is embedded on a surface of Euler genus \(g\), then (i) if \(G\) is 4-connected, \(G\) contains a collection of at most \(b(g)\) paths that cover all the vertices of \(G\) and \(G\) contains a cycle of length at least \(2n/5b(g)\); and (ii) if \(G\) is 3-connected, \(G\) contains a cycle of length at least \(c(g)n^{\log 2/\log 3}\).
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1843837
zbMATH Keywords: face-width
zbMATH Keywords: circumference
zbMATH Keywords: embedding
zbMATH Keywords: Euler genus
zbMATH Keywords: paths
reviewed by: J. W. Moon
MaRDI profile type: Publication
full work available at URL: jctb.2001.2108
OpenAlex ID: W2081444699
cites work: Nonhamiltonian triangulations with large connectivity and representativity
cites work: Trees in Polyhedral Graphs
cites work: 2-connected spanning subgraphs of planar 3-connected graphs
cites work: Relative lengths of paths and cycles in 3-connected graphs
cites work: Spanning trees in locally planar triangulations
cites work: 2‐connected coverings of bounded degree in 3‐connected graphs
cites work: Shortness exponents of families of graphs
cites work: Convex programming and circumference of 3-connected graphs of low genus
cites work: Longest cycles in 3-connected planar graphs
cites work: Generating locally-cyclic triangulations of surfaces
cites work: Graphs on surfaces
cites work: Simple paths on polyhedra
cites work: Graph minors. VII: Disjoint paths on a surface
cites work: On 2-connected spanning subgraphs with low maximum degree
cites work: 4-connected projective planar graphs are Hamiltonian
cites work: A theorem on paths in planar graphs
cites work: Embeddings of graphs with no short noncontractible cycles
cites work: Five-coloring maps on surfaces
cites work: Trees in triangulations
cites work: Color-critical graphs on a fixed surface
cites work: A Theorem on Planar Graphs
cites work: Disjoint paths, planarizing cycles, and spanning walks
DOI: 10.1006/JCTB.2001.2108
description: scientific article; zbMATH DE number 1843837