کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777649 | 1632971 | 2017 | 28 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the Corrádi-Hajnal theorem and a question of Dirac
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Enomoto and Wang refined the Corrádi-Hajnal Theorem, proving the following Ore-type version: For all kâ¥1 and nâ¥3k, every graph G on n vertices contains k disjoint cycles, provided that d(x)+d(y)â¥4kâ1 for all distinct nonadjacent vertices x,y. We refine this further for kâ¥3 and nâ¥3k+1: If G is a graph on n vertices such that d(x)+d(y)â¥4kâ3 for all distinct nonadjacent vertices x,y, then G has k vertex-disjoint cycles if and only if the independence number α(G)â¤nâ2k and G is not one of two small exceptions in the case k=3. We also show how the case k=2 follows from Lovász' characterization of multigraphs with no two disjoint cycles.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 121-148
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 121-148
نویسندگان
H.A. Kierstead, A.V. Kostochka, E.C. Yeager,