کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649545 | 1342459 | 2008 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the minimum degree forcing F-free graphs to be (nearly) bipartite
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let β(G)β(G) denote the minimum number of edges to be removed from a graph G to make it bipartite. For each 3-chromatic graph F we determine a parameter ξ(F)ξ(F) such that for each F-free graph G on n vertices with minimum degree δ(G)⩾2n/(ξ(F)+2)+o(n)δ(G)⩾2n/(ξ(F)+2)+o(n) we have β(G)=o(n2)β(G)=o(n2), while there are F-free graphs H with δ(H)≥⌊2n/(ξ(F)+2)⌋δ(H)≥⌊2n/(ξ(F)+2)⌋ for which β(H)=Ω(n2)β(H)=Ω(n2).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 17, 6 September 2008, Pages 3998–4002
Journal: Discrete Mathematics - Volume 308, Issue 17, 6 September 2008, Pages 3998–4002
نویسندگان
Tomasz Łuczak, Miklós Simonovits,