2019/11/22 by Fukasaku, Ryoya, Furuya, Michitaka, Higashitani, Akihiro
#05C15 #05C76 #13P10 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1911.09799
For a graph G, let χ(G) denote the chromatic number. In graph theory, the following famous conjecture posed by Hedetniemi has been studied: For two graphs G and H, χ(G× H)=min\χ(G),χ(H)\, where G × H is the tensor product of G and H. In this paper, we give a reduction of Hedetniemi's conjecture to an inclusion relation problem on ideals of polynomial rings, and we demonstrate computational experiments for partial solutions of Hedetniemi's conjecture along such a strategy using Gröbner basis.