Describing 3-paths in normal plane maps

O. V. Borodin, A. O. Ivanova, T. R. Jensen, A. V. Kostochka, M. P. Yancey

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)2702-2711
Number of pages10
JournalDiscrete Mathematics
Volume313
Issue number23
DOIs
StatePublished - 2013

Keywords

  • Normal plane map 3-path
  • Plane graph
  • Structural property
  • Weight

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Describing 3-paths in normal plane maps'. Together they form a unique fingerprint.

Cite this