کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8901139 | 1631730 | 2018 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree
ترجمه فارسی عنوان
در پارتیشن های ریشه ای از گراف های ناقص به یک مجموعه مستطیلی و یک جنگل با حداکثر درجه محدود است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
چکیده انگلیسی
The maximum average degree of G is defined to be mad(G)=max{2|E(H)||V(H)|:HâG}. Borodin and Kostochka (2014) proved that every graph G with mad(G)â¤83 admits an (I, Î2)-partition and every graph G with mad(G)â¤145 admits an (I, Î4)-partition. In this paper, we obtain a strengthening result by showing that for any kâ¯â¥â¯2, every graph G with mad(G)â¤2+kk+1 admits an (I, Fk)-partition. As a corollary, every planar graph with girth at least 7 admits an (I, F4)-partition and every planar graph with girth at least 8 admits an (I, F2)-partition. The later result is best possible since neither girth condition nor the class of F2 can be further improved.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 326, 1 June 2018, Pages 117-123
Journal: Applied Mathematics and Computation - Volume 326, 1 June 2018, Pages 117-123
نویسندگان
Min Chen, Weiqiang Yu, Weifan Wang,