کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777659 | 1632971 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Ramsey goodness of paths
ترجمه فارسی عنوان
رمزی خوب مسیرها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Given a pair of graphs G and H, the Ramsey number R(G,H) is the smallest N such that every red-blue coloring of the edges of the complete graph KN contains a red copy of G or a blue copy of H. If graph G is connected, it is well known and easy to show that R(G,H)â¥(|G|â1)(Ï(H)â1)+Ï(H), where Ï(H) is the chromatic number of H and Ï the size of the smallest color class in a Ï(H)-coloring of H. A graph G is called H-good if R(G,H)=(|G|â1)(Ï(H)â1)+Ï(H). The notion of Ramsey goodness was introduced by Burr and ErdÅs in 1983 and has been extensively studied since then. In this short note we prove that n-vertex path Pn is H-good for all nâ¥4|H|. This proves in a strong form a conjecture of Allen, Brightwell, and Skokan.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 384-390
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 384-390
نویسندگان
Alexey Pokrovskiy, Benny Sudakov,