Spanning trees in locally planar triangulations
type: Item
instance of: scholarly article
title: Spanning trees in locally planar triangulations
zbMATH Open document ID: 0802.05033
published in: Journal of Combinatorial Theory. Series B
publication date: 1994-12-01T00:00:00Z
review text: Thomassen has recently shown that a triangulation of the orientable surface of genus \(g\) has a spanning tree of maximum degree at most 4, provided every noncontractible cycle has length at least \(2^{3g+4}\). We show that a 4-connected triangulation of the orientable surface of genus \(g\) has a spanning tree of maximum degree at most 3, provided that every noncontractible cycle has length at least \(2^{3g+5}\). This proves a result suggested by Thomassen. Examples demonstrate that some condition on the length of the noncontractible cycles is necessary for a result of this kind.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 638659
zbMATH Keywords: triangulation
zbMATH Keywords: orientable surface
zbMATH Keywords: spanning tree
zbMATH Keywords: noncontractible cycle
author: M. N. Ellingham
author: Zhicheng Gao
MaRDI profile type: Publication
full work available at URL: jctb.1994.1043
OpenAlex ID: W1977237281
DOI: 10.1006/JCTB.1994.1043
description: scientific article; zbMATH DE number 638659