Tensor product of graphs

As an operation on binary relations, the tensor product was introduced by Alfred North Whitehead and Bertrand Russell in their Principia Mathematica (1912).

It is also equivalent to the Kronecker product of the adjacency matrices of the graphs.

Imrich (1998) gives a polynomial time algorithm for recognizing tensor product graphs and finding a factorization of any such graph.

The Hedetniemi conjecture, which gave a formula for the chromatic number of a tensor product, was disproved by Yaroslav Shitov (2019).

Let G0 denote the underlying set of vertices of the graph G. The internal hom [G, H] has functions f : G0 → H0 as vertices and an edge from f : G0 → H0 to f' : G0 → H0 whenever an edge {x, y} in G implies {f (x), f ' (y)} in H.[4]