Spanning trees in locally planar triangulations (Q1333338): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.1994.1043 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1977237281 / rank | |||
Normal rank |
Latest revision as of 00:19, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Spanning trees in locally planar triangulations |
scientific article |
Statements
Spanning trees in locally planar triangulations (English)
0 references
1 December 1994
0 references
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.
0 references
triangulation
0 references
orientable surface
0 references
spanning tree
0 references
noncontractible cycle
0 references