کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4653192 1632758 2017 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Kempe equivalence of colourings of cubic graphs
ترجمه فارسی عنوان
هم ارزی کمپ رنگ آمیزی نمودارهای مکعبی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Given a graph G=(V,E)G=(V,E) and a proper vertex colouring of GG, a Kempe chain is a subset of VV that induces a maximal connected subgraph of GG 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≥3k≥3, all kk-colourings of connected kk-regular graphs that are not complete are Kempe equivalent. We address the case k=3k=3 by showing that all 33-colourings of a connected cubic graph GG are Kempe equivalent unless GG is the complete graph K4K4 or the triangular prism.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 59, January 2017, Pages 1–10
نویسندگان
, , ,