کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949579 | 1440194 | 2017 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Vertex-colouring of 3-chromatic circulant graphs
ترجمه فارسی عنوان
رنگ آمیزی ورتکس از نمودارهای رنگی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودارهای حلقه ورتکس رنگ آمیزی، شماره کروماتیک،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A circulant graph Cn(a1,â¦,ak) is a graph with n vertices {v0,â¦,vnâ1} such that each vertex vi is adjacent to vertices v(i+aj)modn, for j=1,â¦,k. In this paper we investigate the vertex colouring problem on circulant graphs. We approach the problem in a purely combinatorial way based on an array representation and propose an exact O(k3log2n+n) algorithm for a subclass of 3-chromatic Cn(a1,â¦,ak)'s with kâ¥2, which are characterized in the paper.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 229, 1 October 2017, Pages 121-138
Journal: Discrete Applied Mathematics - Volume 229, 1 October 2017, Pages 121-138
نویسندگان
S. Nicoloso, U. Pietropaoli,