کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8902953 | 1632397 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Splitting a planar graph of girth 5 into two forests with trees of small diameter
ترجمه فارسی عنوان
تقسیم یک نمودار مسطح از محدوده 5 به دو جنگل با درختان با قطر کوچک
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
In 1985, Mihok and recently Axenovich, Ueckerdt, and Weiner asked about the minimum integer gâ>3 such that every planar graph with girth at least gâ admits a 2-colouring of its vertices where the length of every monochromatic path is bounded from above by a constant. By results of Glebov and Zambalaeva and of Axenovich et al., it follows that 5â¤gââ¤6. In this paper we establish that gâ=5. Moreover, we prove that every planar graph of girth at least 5 admits a 2-colouring of its vertices such that every monochromatic component is a tree of diameter at most 6. We also present the list version of our result.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 7, July 2018, Pages 2058-2067
Journal: Discrete Mathematics - Volume 341, Issue 7, July 2018, Pages 2058-2067
نویسندگان
Aleksey N. Glebov,