کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
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
ترجمه فارسی عنوان
در پارتیشن های ریشه ای از گراف های ناقص به یک مجموعه مستطیلی و یک جنگل با حداکثر درجه محدود است
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
چکیده انگلیسی
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
نویسندگان
, , ,