Triangles with restricted degrees of their boundary vertices in plane triangulations

A triangle incident with vertices of degrees a, b and c is said to be an ( a, b, c)-triangle. We prove that every plane triangulation contains an ( a, b, c)-triangle where ( a, b, c) ϵ {(3, 4, c), 4 ⩽ c ⩽ 35; (3, 5, c), 5 ⩽ c ⩽ 21; (3, 6, c), 6 ⩽ c ⩽ 20; (3, 7, c), 7 ⩽ c ⩽ 16; (3, 8, c), 8 ⩽ c ⩽ 14;...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 1999, Vol.196 (1), p.177-196
Main Author: Jendrol', Stanislav
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A triangle incident with vertices of degrees a, b and c is said to be an ( a, b, c)-triangle. We prove that every plane triangulation contains an ( a, b, c)-triangle where ( a, b, c) ϵ {(3, 4, c), 4 ⩽ c ⩽ 35; (3, 5, c), 5 ⩽ c ⩽ 21; (3, 6, c), 6 ⩽ c ⩽ 20; (3, 7, c), 7 ⩽ c ⩽ 16; (3, 8, c), 8 ⩽ c ⩽ 14; (3, 9, c), 9 ⩽ c ⩽ 14; (3, 10, c), 10 ⩽ c ⩽ 13; (4, 4, c), c ⩾ 4; (4, 5, c), 5 ⩽ c ⩽ 13; (4, 6, c), 6 ⩽ c ⩽ 17; (4, 7, c), 7 ⩽ c ⩽ 8; (5, 5, c), 5 ⩽ c ⩽ 7; (5, 6, 6)}. Moreover, we provide lower bounds for the maximum values c in all cases mentioned above. This result strengthens classical results by Lebesgue and Kotzig and a recent result by Borodin.
ISSN:0012-365X
1872-681X
DOI:10.1016/S0012-365X(98)00172-1