Article ID Journal Published Year Pages File Type
4647404 Discrete Mathematics 2014 15 Pages PDF
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),(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).(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,∞)(4,4,∞) and (4,6,11)(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),(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)(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),(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).(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),(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).(4,4,∞),(4,5,11),(4,6,10),(4,7,7),(5,5,7),(5,6,6).

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,