کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656708 1632975 2016 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures
چکیده انگلیسی

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
نویسندگان
, , ,