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.
