کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777225 | 1632576 | 2016 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the chromatic number of (P5, K2,t)-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this paper we study the chromatic number of (P5, K2,t)-free graphs with tâ¥2. It is still an open question whether there are polynomial (Ï-binding) functions fk for kâ¥5 such that every Pk-free graph G satisfies Ï(G)â¤fk(Ï(G)), where Pk is an induced path on k vertices. Our main result is that every (P5, K2,t)-free graph G admits a polynomial Ï-binding function. Moreover, we will present polynomial Ï-binding functions for several other subclasses of P5-free graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 55, November 2016, Pages 127-130
Journal: Electronic Notes in Discrete Mathematics - Volume 55, November 2016, Pages 127-130
نویسندگان
Christoph Brause, Trung Duy Doan, Ingo Schiermeyer,