کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656913 1343700 2012 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Nested cycles in large triangulations and crossing-critical graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Nested cycles in large triangulations and crossing-critical graphs
چکیده انگلیسی

We show that every sufficiently large plane triangulation has a large collection of nested cycles that either are pairwise disjoint, or pairwise intersect in exactly one vertex, or pairwise intersect in exactly two vertices. We apply this result to show that for each fixed positive integer k, there are only finitely many k-crossing-critical simple graphs of average degree at least six. Combined with the recent constructions of crossing-critical graphs given by Bokal, this settles the question of for which numbers q>0 there is an infinite family of k-crossing-critical simple graphs of average degree q.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 102, Issue 1, January 2012, Pages 86-92