Kempe Classes and Almost Bipartite Graphs

Abstract: Let

G

be a graph and

k

be a positive integer, and let

K c (G, k)

denote the number of Kempe equivalence classes for the

k

-colorings of

G

. In 2006, Mohar noted that

K c (G, k) = 1

if

G

is bipartite. As a generalization, we show that

K c (G, k) = 1

if

G

is formed from a bipartite graph by adding any number of edges less than

. We show that our result is tight (up to lower order terms) by constructing, for each

k g e q 8

, a graph

G

formed from a bipartite graph by adding

(k^{2} + 8 k - 45 + 1) / 4

edges such that

K c (G, k) g e q 2

. This refutes a recent conjecture of Higashitani--Matsumoto.

This page was built for publication: Kempe Classes and Almost Bipartite Graphs