کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650491 | 1342489 | 2007 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Erdős–Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We prove that for any orientable surface S and any non-negative integer k , there exists an integer fS(k)fS(k) such that every graph G embeddable in S has either k vertex-disjoint odd cycles or a vertex set A of cardinality at most fS(k)fS(k) such that G-AG-A is bipartite. Such a property is called the Erdős–Pósa property for odd cycles. We also show its edge version. As Reed [Mangoes and blueberries, Combinatorica 19 (1999) 267–296] pointed out, the Erdős–Pósa property for odd cycles do not hold for all non-orientable surfaces.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issue 6, 28 March 2007, Pages 764–768
Journal: Discrete Mathematics - Volume 307, Issue 6, 28 March 2007, Pages 764–768
نویسندگان
Ken-Ichi Kawarabayashi, Atsuhiro Nakamoto,