Examining Kempe equivalence via commutative algebra
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915900263759872 |
|---|---|
| author | Ohsugi, Hidefumi Tsuchiya, Akiyoshi |
| author_facet | Ohsugi, Hidefumi Tsuchiya, Akiyoshi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_06027 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Examining Kempe equivalence via commutative algebra Ohsugi, Hidefumi Tsuchiya, Akiyoshi Combinatorics Commutative Algebra 05C15, 13P10, 13F65 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. |
| title | Examining Kempe equivalence via commutative algebra |
| topic | Combinatorics Commutative Algebra 05C15, 13P10, 13F65 |
| url | https://arxiv.org/abs/2401.06027 |