TY - JOUR
T1 - Describing faces in plane triangulations Dedicated to Douglas R. Woodall on the occasion of his 70th birthday
AU - Borodin, O. V.
AU - Ivanova, A. O.
AU - Kostochka, A. V.
N1 - Funding Information:
The work of the first author was supported by grants 12-01-00631 and 12-01-00448 of the Russian Foundation for Basic Research . The second author was supported by grants 12-01-00631 and 12-01-98510 of the Russian Foundation for Basic Research . The research of the third author is supported in part by NSF grant DMS-1266016 .
PY - 2014/3/28
Y1 - 2014/3/28
N2 - 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).
AB - 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).
KW - 3-polytope
KW - Lebesgue's theorem
KW - Planar graph
KW - Plane triangulation
KW - Structure properties
KW - Weight
UR - http://www.scopus.com/inward/record.url?scp=84890516871&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84890516871&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2013.11.021
DO - 10.1016/j.disc.2013.11.021
M3 - Article
AN - SCOPUS:84890516871
SN - 0012-365X
VL - 319
SP - 47
EP - 61
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1
ER -