کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431268 | 688489 | 2015 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of determining the irregular chromatic index of a graph
ترجمه فارسی عنوان
در پیچیدگی تعیین شاخص نامنظم رنگی یک گراف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
لبه رنگ آمیزی، شاخص رنگی نامنظم، نمودار نامنظم، نمودار محلی محلی نامنظم است
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
An undirected simple graph G is locally irregular if adjacent vertices of G have different degrees. An edge-colouring ϕ of G is locally irregular if each colour class of ϕ induces a locally irregular subgraph of G . The irregular chromatic index χirr′(G) of G is the least number of colours used by a locally irregular edge-colouring of G (if any). We show that the problem of determining the irregular chromatic index of a graph can be handled in linear time when restricted to trees, but it remains NP-complete in general.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 30, January 2015, Pages 113–127
Journal: Journal of Discrete Algorithms - Volume 30, January 2015, Pages 113–127
نویسندگان
Olivier Baudon, Julien Bensmail, Éric Sopena,