Vizing's edge-recoloring conjecture holds

2023/02/24 by Narboni, Jonathan · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2302.12914

Abstract

In 1964 Vizing proved that starting from any k-edge-coloring of a graph G one can reach, using only Kempe swaps, a (Δ + 1)-edge-coloring of G where Δ is the maximum degree of G. One year later he conjectured that one can also reach a Δ-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 graphs.

Cited by

• Kempe changes in H-free graphs

Related

• On an Edge Precoloring Conjecture
• On Vizing's edge colouring question
• The planar edge-coloring theorem of Vizing in O(nlog n) time
• A verified implementation of the Misra and Gries edge coloring algorithm
• Vizing's Theorem in Near-Linear Time