Portal de Periódicos da CAPES

Describing 3-paths in normal plane maps

2013; Elsevier BV; Volume: 313; Issue: 23 Linguagem: Inglês

10.1016/j.disc.2013.08.018

1872-681X

O.V. Borodin, A. O. Ivanova, Torben R. Jensen, Alexandr Kostochka, Matthew Yancey,

Mathematics and Applications

We prove that every normal plane map, as well as every 3-polytope, has a path on three vertices whose degrees are bounded from above by one of the following triplets: (3,3,∞), (3,4,11), (3,7,5), (3,10,4), (3,15,3), (4,4,9), (6,4,8), (7,4,7), and (6,5,6). No parameter of this description can be improved, as shown by appropriate 3-polytopes.