کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4657074 | 1632990 | 2010 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Claw-free graphs VI. Colouring
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this paper we prove that if G is a connected claw-free graph with three pairwise non-adjacent vertices, with chromatic number χ and clique number ω, then χ⩽2ω and the same for the complement of G. We also prove that the choice number of G is at most 2ω, except possibly in the case when G can be obtained from a subgraph of the Schläfli graph by replicating vertices. Finally, we show that the constant 2 is best possible in all cases.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 100, Issue 6, November 2010, Pages 560-572
Journal: Journal of Combinatorial Theory, Series B - Volume 100, Issue 6, November 2010, Pages 560-572