Revised Kempe-class conjecture for almost bipartite graphs

About 3 years old · traced to

Let GG be a graph formed from a bipartite graph BB by adding ℓ\ell edges, so that GG is a (k−1)(k-1)-colorable B+EℓB+E_\ell graph. For a graph GG and positive integer kk, let Kc⁡(G,k)\operatorname{Kc}(G,k) denote the number of equivalence classes of kk-colorings, where two colorings are equivalent if one can be transformed into the other by a sequence of Kempe swaps. Let 1k−1\mathbf{1}_{k-1} denote the indicator of the relevant condition on k−1k-1 as used in the source.

Revised Kempe-class conjecture. If GG is a (k−1)(k-1)-colorable B+EℓB+E_\ell graph with k≥4k\geq 4 and

ℓ<k2+8k−45+1k−14,\ell<\frac{k^2+8k-45+\mathbf{1}_{k-1}}{4},

then

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

This is proposed as a revised version after the original conjecture was disproved in part of its range. The supplied text does not state whether the revised conjecture has been proved or refuted.

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.