An algebraic reduction of Hedetniemi's conjecture

MaRDI QIDQ6329675zbMATH OpenFDO

Authors Ryoya Fukasaku, Michitaka Furuya, Akihiro Higashitani

Publication date 21 November 2019

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)

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.

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)