کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651904 1632582 2015 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Kempe Equivalence of Colourings of Cubic Graphs
ترجمه فارسی عنوان
کمپه همبستگی رنگ آمیزی نمودارهای مکعبی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Given a graph G=(V,E) and a proper vertex colouring of G, a Kempe chain is a subset of V that induces a maximal connected subgraph of G in which every vertex has one of two colours. To make a Kempe change is to obtain one colouring from another by exchanging the colours of vertices in a Kempe chain. Two colourings are Kempe equivalent if each can be obtained from the other by a series of Kempe changes. A conjecture of Mohar asserts that, for k≥3, all k-colourings of connected k-regular graphs that are not complete are Kempe equivalent. We address the case k=3 by showing that all 3-colourings of a connected cubic graph G are Kempe equivalent unless G is the complete graph K4 or the triangular prism.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 243-249