Kempe Classes and Almost Bipartite Graphs

Abstract

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{}{}{0ex}{}{\lceil k/2\rceil }{2}\right)+\left(\genfrac{}{}{0ex}{}{\lfloor k/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)/4$ edges such that $Kc(G,k)\ge 2$. This refutes a recent conjecture of Higashitani--Matsumoto.

7 pages, 2 figures; 2nd version incorporates reviewer feedback