Vizing‘s edge-recoloring conjecture holds.
EUROCOMB’23
Abstract
Pages:
740–747
In 1964 Vizing proved that starting from any $k$-edge-coloring of a graph $G$ one can reach, using only Kempe swaps, a $(\Delta+1)$-edge-coloring of $G$ where $\Delta$ is the maximum degree of $G$. One year later he conjectured that one can also reach a $\Delta$-edge-coloring of $G$ if there exists one. Bonamy et. al proved that the conjecture is true for the case of triangle-free graphs. In this paper we prove the conjecture for all simple graphs.
740–747
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Jonathan Narboni