کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871134 | 1440178 | 2018 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
k-tuple colorings of the Cartesian product of graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A k-tuple coloring of a graph G assigns a set of k colors to each vertex of G such that if two vertices are adjacent, the corresponding sets of colors are disjoint. The k-tuple chromatic number of G, Ïk(G), is the smallest t so that there is a k-tuple coloring of G using t colors. It is well known that Ï(Gâ¡H)=max{Ï(G),Ï(H)}. In this paper, we show that there exist graphs G and H such that Ïk(Gâ¡H)>max{Ïk(G),Ïk(H)} for kâ¥2. Moreover, we also show that there exist graph families such that, for any kâ¥1, the k-tuple chromatic number of their Cartesian product is equal to the maximum k-tuple chromatic number of its factors.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 245, 20 August 2018, Pages 177-182
Journal: Discrete Applied Mathematics - Volume 245, 20 August 2018, Pages 177-182
نویسندگان
Flavia Bonomo, Ivo Koch, Pablo Torres, Mario Valencia-Pabon,