کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656830 1632984 2014 62 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Colouring graphs when the number of colours is almost the maximum degree
ترجمه فارسی عنوان
رنگ آمیزی نمودار زمانی که تعداد رنگ تقریبا حداکثر درجه یک است؟
کلمات کلیدی
شماره کروماتیک، قضیه بروکس
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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