Describing faces in plane triangulations Dedicated to Douglas R. Woodall on the occasion of his 70th birthday

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

Research output: Contribution to journalArticlepeer-review

Abstract

Lebesgue (1940) proved that every plane triangulation contains a face with the vertex-degrees majorized by one of the following triples: (3,6,∞),(3,7,41),(3,8,23),(3,9,17),(3,10,14),(3,11,13),(4,4,∞),(4,5, 19),(4,6,11),(4,7,9),(5,5,9),(5,6,7). Jendrol' (1999) improved this description, except for (4,4,∞) and (4,6,11), to (3,4,35),(3,5,21),(3,6,20),(3,7,16), (3,8,14),(3,9,14),(3,10,13),(4,4,∞),(4,5,13),(4,6,17),(4,7,8),(5,5,7),(5, 6,6) and conjectured that the tight description is (3,4,30),(3,5,18),(3,6,20), (3,7,14),(3,8,14),(3,9,12),(3,10,12),(4,4,∞),(4,5,10),(4,6,15),(4,7,7),(5, 5,7),(5,6,6). We prove that in fact every plane triangulation contains a face with the vertex-degrees majorized by one of the following triples, where every parameter is tight: (3,4,31),(3,5,21),(3,6,20),(3,7,13),(3,8,14),(3,9,12),(3,10, 12),(4,4,∞),(4,5,11),(4,6,10),(4,7,7),(5,5,7),(5,6,6).

Original languageEnglish (US)
Pages (from-to)47-61
Number of pages15
JournalDiscrete Mathematics
Volume319
Issue number1
DOIs
StatePublished - Mar 28 2014

Keywords

  • 3-polytope
  • Lebesgue's theorem
  • Planar graph
  • Plane triangulation
  • Structure properties
  • Weight

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Describing faces in plane triangulations Dedicated to Douglas R. Woodall on the occasion of his 70th birthday'. Together they form a unique fingerprint.

Cite this