Examining Kempe equivalence via commutative algebra

Kempe equivalence is a classical and important notion on vertex coloring in graph theory.

In this talk, I introduce several ideals associated with graphs and provide a method determine whether two k-colorings are Kempe equivalent via commutative algebra. Moreover, I give a way to compute all k-colorings of a graph up to Kempe equivalence by virtue of the algebraic technique on Gröbner bases.

This talk is based on joint work with Hidefumi Ohsugi.