کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656830 | 1632984 | 2014 | 62 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Colouring graphs when the number of colours is almost the maximum degree
ترجمه فارسی عنوان
رنگ آمیزی نمودار زمانی که تعداد رنگ تقریبا حداکثر درجه یک است؟
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شماره کروماتیک، قضیه بروکس
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We consider the chromatic number of graphs with maximum degree Δ. For sufficiently large Δ, we determine the precise values of k for which the barrier to (Δ+1−k)(Δ+1−k)-colourability must be a local condition, i.e. a small subgraph. We also show that for Δ constant and sufficiently large, (Δ+1−k)(Δ+1−k)-colourability is either NP-complete or can be solved in linear time, and we determine precisely which values of k correspond to each case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 109, November 2014, Pages 134–195
Journal: Journal of Combinatorial Theory, Series B - Volume 109, November 2014, Pages 134–195
نویسندگان
Michael Molloy, Bruce Reed,