Kempe Classes and Almost Bipartite Graphs

Let $G$ be a graph and $k$ be a positive integer, and let $Kc(G,k)$ denote the number of Kempe equivalence classes for the $k$-colorings of $G$. In 2006, Mohar noted that $Kc(G,k)=1$ if $G$ is bipartite. As a generalization, we show that $Kc(G,k)=1$ if $G$ is formed from a bipartite graph by adding any number of edges less than $\left(\genfrac{}{}{0px}{}{\lceil k\mathrm{/}2\rceil }{2}\right)+\left(\genfrac{}{}{0px}{}{\lfloor k\mathrm{/}2\rfloor }{2}\right)$. We show that our result is tight (up to lower order terms) by constructing, for each $k\ge 8$, a graph $G$ formed from a bipartite graph by adding $(k^2+8k-45+1)\mathrm{/}4$ edges such that $Kc(G,k)\ge 2$. This refutes a recent conjecture of Higashitani–Matsumoto.