An algebraic reduction of Hedetniemi's conjecture

arXiv1911.09799MaRDI QIDQ6329675FDOQ6329675

Ryoya Fukasaku, Akihiro Higashitani, Michitaka Furuya

Publication date: 21 November 2019

Abstract: For a graph $G$, let $chi(G)$ denote the chromatic number. In graph theory, the following famous conjecture posed by Hedetniemi has been studied: For two graphs $G$ and $H$, $chi(GimesH)=minchi(G),chi(H)$, where $GimesH$ 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"{o}bner basis.

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

This page was built for publication: An algebraic reduction of Hedetniemi's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6329675)