On Vizing's edge colouring question (Q2680572)

Given a proper edge-coloring of a graph, a Kempe change consists of selecting a maximally connected two-coloured subgraph and swapping the corresponding two colours, this operation yields a new proper edge-coloring. Kempe changes are an essential tool in the proof of Vizing's theorem that every graph \(G\) satisfies \(\chi^\prime(G) \leq \Delta(G) + 1\). The current paper studies a problem in ``combinatorial reconfiguration'': starting from an arbitrary edge-colouring, it is possible to arrive at a given edge-coloring via Kempe changes? The authors show that given any graph \(G\) and any \(k > \chi^\prime(G)\), any given \(\chi^\prime(G)\)-edge-coloring can be reached from any \(k\)-edge-coloring via a sequence of Kempe changes, under the additional assumption that \(G\) is triangle-free. This solves a particular case of a question posed by \textit{V. G. Vizing} [Russ. Math. Surv. 23, No. 6, 125--141 (1968; Zbl 0192.60502); translation from Usp. Mat. Nauk 23, No. 6(144), 117--134 (1968)].