کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656708 | 1632975 | 2016 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Gyárfás conjectured in 1985 that for all k, ℓ, every graph with no clique of size more than k and no odd hole of length more than ℓ has chromatic number bounded by a function of k, ℓ. We prove three weaker statements:
• Every triangle-free graph with sufficiently large chromatic number has an odd hole of length different from five;
• For all ℓ, every triangle-free graph with sufficiently large chromatic number contains either a 5-hole or an odd hole of length more than ℓ;
• For all k, ℓ, every graph with no clique of size more than k and sufficiently large chromatic number contains either a 5-hole or a hole of length more than ℓ.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 118, May 2016, Pages 109–128
Journal: Journal of Combinatorial Theory, Series B - Volume 118, May 2016, Pages 109–128
نویسندگان
Maria Chudnovsky, Alex Scott, Paul Seymour,