The 3-connected degree-swappability conjecture
The 3-connected degree-swappability conjecture
Let be a graph. A degree-assignment for assigns to each vertex a list of colors with , and two -colorings are -equivalent if one can be obtained from the other by a sequence of Kempe changes. The graph is degree-swappable if, for every degree-assignment , all -colorings of are -equivalent.
Degree-swappability conjecture. Every -connected graph distinct from the complete graph and the triangular prism is degree-swappable.
This conjecture would strengthen the theorem that every -connected graph distinct from the complete graph is degree-swappable. Earlier work gives examples of -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.