  A $50$ years unsolved conjecture by Hedetniemi [{\it Homomorphisms of graphs
and automata, \newblock {\em Thesis (Ph.D.)--University of Michigan}, 1966}]
asserts that the chromatic number of the categorical product of two graphs $G$
and $H$ is $\min\{\chi(G),\chi(H)\}$. The present authors [{\it On the
chromatic number of general {K}neser hypergraphs. \newblock {\em Journal of
Combinatorial Theory, Series B}, 2015.}] introduced the altermatic and the
strong altermatic number of graphs as two tight lower bounds for the chromatic
number of graphs. In this work, we prove a relaxation of Hedetniemi's
conjecture in terms of strong altermatic number. Also, we present a tight lower
bound for the chromatic number of the categorical product of two graphs in term
of their altermatic and strong altermatic numbers. These results enrich the
family of pair graphs $\{G,H\}$ satisfying Hedetniemi's conjecture.
