Irreducible Triangulations of Surfaces

✍ Scribed by Z. Gao; R.B. Richter; P.D. Seymour

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 346 KB
• Volume: 68
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1996.0064

✦ Synopsis

In this note we show that, for any surface 7 and any k, there are at most finitely many triangulations of 7 such that each edge is in a noncontractible cycle of length k and is in no shorter noncontractible cycle. Such a triangulation is k-irreducible. This is equivalent to the statement that for any surface 7 and any k, there are at most finitely many embeddings in 7 that are minor minimal with representativity k.

This last fact can be derived from a theorem (a variant of Wagner's conjecture) that graphs embedded in a surface, with vertices and edges labelled from a well-quasi-order, form a well-quasi-order under abstract minors respecting the labels. However, this proof is very complicated and is not constructive. Thus, it is desirable to have an elementary proof of this particular consequence.

Recently, several papers have dealt with the problem of showing that there are at most finitely many 3-irreducible triangulations [BE, GRT, NO]. Malnic$ and Mohar [MM] prove that there are at most finitely many 4-irreducible triangulations of an orientable surface. Malnic$ and Nedela [MN] have given the first elementary proof that the number of k-irreducible triangulations of 7 is finite for all k and all 7. Gao et al.

[GRT] have a very simple proof that there are at most c! 4 vertices in a 3-irreducible triangulation of any surface (orientable or not) with Euler characteristic 2&!, while Nakamota and Ota [NO] show (with a similar simple proof) that in fact there are at most c! vertices in such a triangulation.

In this note, we give a very short, simple proof of the Malnic$ and Nedela theorem. Moreover, we give an explicit estimate of the form c k ! 2 on the article no. 0064 206 0095-8956Â96 18.00