Vizing's edge-recoloring conjecture
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
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.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.