کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9514594 | 1632609 | 2005 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On some arboricities in planar graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The arboricity a(G) of a graph G is the minimum number of forests needed to cover the edges of G. For a tree T, we similarly define the T-free arboricity Tfa(G) of G as the minimum number of T-free forests needed to cover the edges of G. We give bounds on the maximum T-free arboricity of a planar graph with girth g for various T and g. One of them solves an open problem of Gyárfás and West: there exist planar graphs with track number 4. We also provide new NP-complete problems in sparse planar graphs. A very elementary one is the problem for any gâ¥4 to determine if a planar bipartite graph with maximum degree three and girth at least g has star arboricity two.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 22, 15 October 2005, Pages 427-432
Journal: Electronic Notes in Discrete Mathematics - Volume 22, 15 October 2005, Pages 427-432
نویسندگان
Daniel Gonçalves, Pascal Ochem,