کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650789 | 1632441 | 2008 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Connectedness of the graph of vertex-colourings
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
For a positive integer k and a graph G, the k-colour graph of G , Ck(G)Ck(G), is the graph that has the proper k-vertex-colourings of G as its vertex set, and two k -colourings are joined by an edge in Ck(G)Ck(G) if they differ in colour on just one vertex of G . In this note some results on the connectedness of Ck(G)Ck(G) are proved. In particular, it is shown that if G has chromatic number k∈{2,3}k∈{2,3}, then Ck(G)Ck(G) is not connected. On the other hand, for k⩾4k⩾4 there are graphs with chromatic number k for which Ck(G)Ck(G) is not connected, and there are k -chromatic graphs for which Ck(G)Ck(G) is connected.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issues 5–6, 28 March 2008, Pages 913–919
Journal: Discrete Mathematics - Volume 308, Issues 5–6, 28 March 2008, Pages 913–919
نویسندگان
Luis Cereceda, Jan van den Heuvel, Matthew Johnson,