کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777359 | 1632751 | 2017 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Partitioning a triangle-free planar graph into a forest and a forest of bounded degree
ترجمه فارسی عنوان
تقسیم کردن یک نمودار مستطیل بدون مثلث به یک جنگل و یک جنگل درجه محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
An (F,Fd)-partition of a graph is a vertex-partition into two sets F and Fd such that the graph induced by F is a forest and the one induced by Fd is a forest with maximum degree at most d. We prove that every triangle-free planar graph admits an (F,F5)-partition. Moreover we show that if for some integer d there exists a triangle-free planar graph that does not admit an (F,Fd)-partition, then it is an NP-complete problem to decide whether a triangle-free planar graph admits such a partition.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 66, December 2017, Pages 81-94
Journal: European Journal of Combinatorics - Volume 66, December 2017, Pages 81-94
نویسندگان
François Dross, Mickael Montassier, Alexandre Pinlou,