کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871482 | 1440186 | 2018 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
ترجمه فارسی عنوان
محدوده تنگی در پیچیدگی رنگ نیمه صحیح گرافهای مکعبی و زیرمجموعه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ نیمه عادلانه، رنگ صحیح، نمودار مکعبی، نمودارهای زیرمجموعه،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A k-coloring of a graph G=(V,E) is called semi-equitable if there exists a partition of its vertex set into independent subsets V1,â¦,Vk in such a way that |V1|ââ{â|V|âkâ,â|V|âkâ} and âVi|â|Vjââ¤1 for each i,j=2,â¦,k. The color class V1 is called non-equitable. In this note we consider the complexity of semi-equitable k-coloring, kâ¥4, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G and constants ϵ>0, kâ¥4, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if sâ¥nâ3+ϵn, and it is polynomially solvable if sâ¤nâ3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 237, 11 March 2018, Pages 116-122
Journal: Discrete Applied Mathematics - Volume 237, 11 March 2018, Pages 116-122
نویسندگان
Hanna FurmaÅczyk, Marek Kubale,