The 3-connected degree-swappability conjecture

Let GG be a graph. A degree-assignment for GG assigns to each vertex vv a list L(v)L(v) of colors with L(v)=dG(v)|L(v)|=d_G(v), and two LL-colorings are LL-equivalent if one can be obtained from the other by a sequence of Kempe changes. The graph GG is degree-swappable if, for every degree-assignment LL, all LL-colorings of GG are LL-equivalent.

Degree-swappability conjecture. Every 33-connected graph distinct from the complete graph and the triangular prism is degree-swappable.

This conjecture would strengthen the theorem that every 44-connected graph distinct from the complete graph is degree-swappable. Earlier work gives examples of 22-connected graphs that are not degree-swappable, so the conjecture concerns the boundary between these known negative and positive results.

Sources & referencesView supporting material

Primary source

Dibyayan Chakraborty, Carl Feghali and Reem Mahmoud, “Kempe Equivalent List Colorings Revisited”, arXiv:2211.16728 (2024).

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.