کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651907 | 1632582 | 2015 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Partitioning a triangle-free planar graph into a forest and a forest of bounded degree
ترجمه فارسی عنوان
تقسیم کردن یک نمودار مستطیل بدون مثلث به یک جنگل و یک جنگل درجه محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We prove that every triangle-free planar graph can have its set of vertices partitioned into two sets, one inducing a forest and the other a forest with maximum degree at most 5. We also show that if for some d, there is a triangle-free planar graph that cannot be partitioned into two sets, one inducing a forest and the other a forest with maximum degree at most d, then it is an NP-complete problem to decide if a triangle-free planar graph admits such a partition.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 269-275
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 269-275