Higashitani–Matsumoto conjecture on Kempe classes of almost bipartite graphs

About 3 years old · traced to

Let GG be a (k−1)(k-1)-colorable B+EℓB+E_\ell graph, where BB is bipartite, EℓE_\ell denotes a set of ℓ\ell added edges, k≥4k\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 k≥8k\ge 8, so the assertion does not hold in the full stated range.

References

Primary source

Daniel W. Cranston and Carl Feghali, “Kempe Classes and Almost Bipartite Graphs”, arXiv:2303.09365 (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.