Tight Descriptions of 3-Paths in Normal Plane Maps: Dedicated to Andre Raspaud on the occasion of his 70th birthday

O. V. Borodin, A. O. Ivanova, A. V. Kostochka

Research output: Contribution to journalArticlepeer-review

Abstract

We prove that every normal plane map (NPM) has a path on three vertices (3-path) whose degree sequence is bounded from above by one of the following triplets: (3, 3, ∞), (3,15,3), (3,10,4), (3,8,5), (4,7,4), (5,5,7), (6,5,6), (3,4,11), (4,4,9), and (6,4,7). This description is tight in the sense that no its parameter can be improved and no term dropped. We also pose a problem of describing all tight descriptions of 3-paths in NPMs and make a modest contribution to it by showing that there exist precisely three one-term descriptions: (5, ∞, 6), (5, 10, ∞), and (10, 5, ∞).

Original languageEnglish (US)
Pages (from-to)115-132
Number of pages18
JournalJournal of Graph Theory
Volume85
Issue number1
DOIs
StatePublished - May 1 2017

Keywords

  • 3-path
  • normal plane map
  • plane graph
  • structural property

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint Dive into the research topics of 'Tight Descriptions of 3-Paths in Normal Plane Maps: Dedicated to Andre Raspaud on the occasion of his 70th birthday'. Together they form a unique fingerprint.

Cite this