Solution of Vizing's Problem on Interchanges for the case of Graphs with Maximum Degree 4 and Related Results

Let G be a Class 1 graph with maximum degree 4 and let t ≥ 5 be an integer. We show that any proper t ‐edge coloring of G can be transformed to any proper 4‐edge coloring of G using only transformations on 2‐colored subgraphs (so‐called interchanges). This settles the smallest previously unsolved case of a well‐known problem of Vizing on interchanges, posed in 1965. Using our result we give an affirmative answer to a question of Mohar for two classes of graphs: we show that all proper 5‐edge colorings of a Class 1 graph with maximum degree 4 are Kempe equivalent, that is, can be transformed to each other by interchanges, and that all proper 7‐edge colorings of a Class 2 graph with maximum degree 5 are Kempe equivalent.