Kempe Equivalence of Edge‐Colorings in Subcubic and Subquartic Graphs
Jessica M. McDonald, Bojan Mohar, Diego Scheide · Journal of Graph Theory · 2011
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