Premium
Kempe Equivalence of Edge‐Colorings in Subcubic and Subquartic Graphs
Author(s) -
McDonald Jessica,
Mohar Bojan,
Scheide Diego
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20613
Subject(s) - mathematics , combinatorics , conjecture , equivalence (formal languages) , edge coloring , graph , enhanced data rates for gsm evolution , cubic graph , discrete mathematics , line graph , voltage graph , graph power , computer science , telecommunications
Abstract It is proved that all 4‐edge‐colorings of a (sub)cubic graph are Kempe equivalent. This resolves a conjecture of the second author. In fact, it is found that the maximum degree Δ = 3 is a threshold for Kempe equivalence of (Δ+1)‐edge‐colorings, as such an equivalence does not hold in general when Δ = 4. One extra color allows a similar result in this latter case; however, namely, when Δ≤4 it is shown that all (Δ+2)‐edge‐colorings are Kempe equivalent. © 2011 Wiley Periodicals, Inc. J Graph Theory