Higashitani–Matsumoto conjecture on Kempe classes of almost bipartite graphs

From papers

Let GG be a (k1)(k-1)-colorable B+EB+E_\ell graph, where BB is bipartite, EE_\ell denotes a set of \ell added edges, k4k\ge 4, and <(k2)\ell<\binom{k}{2}. Let Kc(G,k)\operatorname{Kc}(G,k) denote the number of equivalence classes of kk-colorings of GG under Kempe swaps.

Higashitani–Matsumoto conjecture.

Kc(G,k)=1.\operatorname{Kc}(G,k)=1.

Higashitani and Matsumoto proved the conjecture for k=4k=4. It was subsequently disproved for all k8k\ge 8, so the assertion does not hold in the full stated range.

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

Daniel W. Cranston and Carl Feghali, “Kempe Classes and Almost Bipartite Graphs”, arXiv:2303.09365 (2024).

Solutions 0

No solutions have been posted yet.