2024/01/11 by Ohsugi, Hidefumi, Tsuchiya, Akiyoshi
#05C15 #13F65 #13P10 #Combinatorics (math.CO) #Commutative Algebra (math.AC) #FOS: Mathematics
paper · doi:10.48550/arxiv.2401.06027
Kempe equivalence is a classical and important notion on vertex coloring in graph theory. In the present paper, we introduce several ideals associated with graphs and provide a method to determine whether two k-colorings are Kempe equivalent via commutative algebra. Moreover, we 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. As a consequence, the number of k-Kempe classes can be computed by using Hilbert functions. Finally, we introduce several algebraic algorithms related to Kempe equivalence.