کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653192 | 1632758 | 2017 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Kempe equivalence of colourings of cubic graphs
ترجمه فارسی عنوان
هم ارزی کمپ رنگ آمیزی نمودارهای مکعبی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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
Journal: European Journal of Combinatorics - Volume 59, January 2017, Pages 1–10
نویسندگان
Carl Feghali, Matthew Johnson, Daniël Paulusma,