Hedetniemi's conjecture, disproved by Shitov (2019), asserted that the chromatic number of the graph tensor product of
any two finite simple graphs and
, each with at least one graph
vertex, satisfies
where
denotes the chromatic number (Hedetniemi 1966).
A minimum vertex coloring of gives a vertex coloring
of
by assigning the graph vertex
the color of
. Applying the same argument to
shows that
always holds (Shitov 2019, p. 663).
El-Zahar and Sauer (1985) proved that equality holds whenever . Tardif (2023) showed that there
are simple graphs
and
with
but
.
Thus 5 is the smallest possible value of the smaller factor chromatic
number in a counterexample.