کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141563 | 957025 | 2009 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Graph coloring with cardinality constraints on the neighborhoods
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph GG a kk-coloring, i.e., a partition V1,…,VkV1,…,Vk of the vertex set of GG such that, for some specified neighborhood Ñ(v) of each vertex vv, the number of vertices in Ñ(v)∩Vi is (at most) a given integer hvi. The complexity of some variations is discussed according to Ñ(v), which may be the usual neighbors, or the vertices at distance at most 2, or the closed neighborhood of vv (vv and its neighbors). Polynomially solvable cases are exhibited (in particular when GG is a special tree).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 6, Issue 4, November 2009, Pages 362–369
Journal: Discrete Optimization - Volume 6, Issue 4, November 2009, Pages 362–369
نویسندگان
M.-C. Costa, D. de Werra, C. Picouleau, B. Ries,