کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656756 1632976 2016 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Highly connected monochromatic subgraphs of two-colored complete graphs
ترجمه فارسی عنوان
زیرگراف‌های تک رنگی بسیار متصل به گرافهای کامل دو رنگ
کلمات کلیدی
اتصال؛ زیرگرافی تک رنگ؛ رنگ آمیزی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

We show that each 2-edge coloring of the complete graph on n vertices leads to a monochromatic k  -connected subgraph on at least n−2(k−1)n−2(k−1) vertices, provided n≥4k−3n≥4k−3. It settles in the affirmative a conjecture of Bollobás and Gyárfás.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 117, March 2016, Pages 88–92
نویسندگان
,