Irreducible triangulations are small

DOI10.1016/J.JCTB.2010.01.004zbMATH Open1203.05035arXiv0907.1421OpenAlexW3099654277MaRDI QIDQ974471FDOQ974471

David R. Wood, Gwenaël Joret

Publication date: 3 June 2010

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: A triangulation of a surface is emph{irreducible} if there is no edge whose contraction produces another triangulation of the surface. We prove that every irreducible triangulation of a surface with Euler genus $ggeq1$ has at most $13g-4$ vertices. The best previous bound was $171g-72$.

Full work available at URL: https://arxiv.org/abs/0907.1421

Recommendations

• Note on irreducible triangulations of surfaces
• scientific article; zbMATH DE number 1979507
• Irreducible triangulations of surfaces with boundary
• Irreducible triangulations of surfaces
• Irreducible triangulations of the once-punctured torus

zbMATH Keywords

topological graph theoryirreducible triangulations

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Graphs on surfaces
• Title not available (Why is that?)
• Irreducible triangulations of the Klein bottle
• Generating the triangulations of the projective plane
• Title not available (Why is that?)
• Note on the irreducible triangulations of the Klein bottle
• Irreducible triangulations of the torus
• On the maximum number of cliques in a graph embedded in a surface
• Hierarchy of surface models and irreducible triangulations.
• How to exhibit toroidal maps in space
• Geometric realization of a triangulation on the projective plane with one face removed
• Generating triangulations on closed surfaces with minimum degree at least 4
• Title not available (Why is that?)
• All orientable 2-manifolds have finitely many minimal triangulations
• Note on irreducible triangulations of surfaces
• All 2-manifolds have finitely many minimal triangulations
• \(N\)-flips in even triangulations on surfaces
• Generating locally-cyclic triangulations of surfaces
• The nonorientable genus is additive
• Constructing the graphs that triangulate both the torus and the Klein bottle
• Diagonal flips in outer-Klein-bottle triangulations
• An additivity theorem for the genus of a graph
• Structural characterization of projective flexibility

Cited In (16)

• The irreducible triangulations of the torus as periodic tessellations of the plane
• Title not available (Why is that?)
• A generating theorem of simple even triangulations with a finitizable set of reductions
• Generating even triangulations on the torus
• Minor relation for quadrangulations on the projective plane
• Hierarchy of surface models and irreducible triangulations.
• Subgraph densities in a surface
• On the maximum number of cliques in a graph embedded in a surface
• Note on irreducible triangulations of surfaces
• On irreducible triangulations of punctured torus and punctured Klein bottle
• Flippable edges in triangulations on surfaces
• A fast algorithm for computing irreducible triangulations of closed surfaces in \(\mathbb{E}^d\)
• Even Embeddings of the Complete Graphs and Their Cycle Parities
• Some triangulated surfaces without balanced splitting
• Finitizable set of reductions for polyhedral quadrangulations of closed surfaces
• Irreducible triangulations of surfaces with boundary

This page was built for publication: Irreducible triangulations are small

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q974471)