کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650834 | 1342504 | 2007 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Caterpillar arboricity of planar graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We solve a conjecture of Roditty, Shoham and Yuster [P.J. Cameron (Ed.), Problems from the 17th British Combinatorial Conference, Discrete Math., 231 (2001) 469–478; Y. Roditty, B. Shoham, R. Yuster, Monotone paths in edge-ordered sparse graphs, Discrete Math. 226 (2001) 411–417] on the caterpillar arboricity of planar graphs. We prove that for every planar graph G=(V,E)G=(V,E), the edge set E can be partitioned into four subsets (Ei)1⩽i⩽4(Ei)1⩽i⩽4 in such a way that G[Ei]G[Ei], for 1⩽i⩽41⩽i⩽4, is a forest of caterpillars. We also provide a linear-time algorithm which constructs for a given planar graph G, four forests of caterpillars covering the edges of G.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issue 16, 28 July 2007, Pages 2112–2121
Journal: Discrete Mathematics - Volume 307, Issue 16, 28 July 2007, Pages 2112–2121
نویسندگان
D. Gonçalves,