Revised Kempe-class conjecture for almost bipartite graphs

Let GG be a graph formed from a bipartite graph BB by adding \ell edges, so that GG is a (k1)(k-1)-colorable B+EB+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 1k1\mathbf{1}_{k-1} denote the indicator of the relevant condition on k1k-1 as used in the source.

Revised Kempe-class conjecture. If GG is a (k1)(k-1)-colorable B+EB+E_\ell graph with k4k\geq 4 and

<k2+8k45+1k14,\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.

Sources & referencesView supporting material

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.