کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648467 1632431 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Decomposing a planar graph with girth at least 8 into a forest and a matching
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Decomposing a planar graph with girth at least 8 into a forest and a matching
چکیده انگلیسی

W. He et al. showed that a planar graph of girth at least 11 can be decomposed into a forest and a matching. A. Bass et al. proved the same statement for planar graphs of girth at least 10. Recently, O.V. Borodin et al. improved the bound on the girth to 9. In this paper, we further improve the bound on the girth to 8. This bound is the best possible in the sense that there are planar graphs with girth 7 that cannot be decomposed into a forest and a matching.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issues 10–11, 6 June 2011, Pages 844–849
نویسندگان
, ,