کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
11263213 | 1722376 | 2019 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Triangle-free planar graphs with small independence number
ترجمه فارسی عنوان
نمودارهای فلزی مثلثی با تعداد کمی استقلال
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Since planar triangle-free graphs are 3-colourable, such a graph with n vertices has an independent set of size at least nâ3. We prove that unless the graph contains a certain obstruction, its independence number is at least nâ(3âε) for some fixed ε>0. We also provide a reduction rule for this obstruction, which enables us to transform any plane triangle-free graph G into a plane triangle-free graph Gâ² such that α(Gâ²)â|Gâ²|â3=α(G)â|G|â3 and|Gâ²|â¤(α(G)â|G|â3)âε. We derive a number of algorithmic consequences as well as a structural description of n-vertex plane triangle-free graphs whose independence number is close to nâ3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 76, February 2019, Pages 88-103
Journal: European Journal of Combinatorics - Volume 76, February 2019, Pages 88-103
نویسندگان
ZdenÄk DvoÅák, Jordan Venters,