Vizing's edge-recoloring conjecture

About 3 years old · traced to

Let GG be a graph, let Δ(G)\Delta(G) 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 kk-edge-coloring of a graph GG is equivalent to a Δ(G)\Delta(G)-edge-coloring of GG 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

Never refreshed

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.