Vizing's edge-recoloring conjecture
Let be a graph, let denote its maximum degree, and let a proper edge-coloring be a coloring of the edges in which adjacent edges receive different colors. Two edge-colorings are equivalent if one can be transformed into the other by a sequence of Kempe swaps.
Vizing's conjecture. Every -edge-coloring of a graph is equivalent to a -edge-coloring of if there is any.
This conjecture asks whether every edge-coloring can be reconfigured to an optimal edge-coloring whenever one exists. The supplied source does not state whether it is resolved.
References
Primary source
Jonathan Narboni, “Vizing's edge-recoloring conjecture holds”, arXiv:2302.12914 (2023).
Additional references
8 papers in this index state this conjecture (2005–2023). The statement above is taken from the most recent of them; the others are arXiv:2301.02140, arXiv:1909.01260, arXiv:1904.12060, arXiv:1805.05996, arXiv:1506.02576, arXiv:1401.4568, arXiv:math/0512518.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.