Examining Kempe equivalence via commutative algebra

  • Akiyoshi Tsuchiya (Toho University)
G3 10 (Lecture hall)


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.

Mirke Olschewski

MPI for Mathematics in the Sciences Contact via Mail

Upcoming Events of This Seminar