# Coloring tensor products of graphs

Let $G,H$ are simple finite graphs and $A = G \times H$. Here $G \times H$ is the tensor product (also called the direct or categorical product) of $G$ and $H$.

Let $G$ has smaller chromatic number. Experiments suggest that given a coloring $f$ of $G$ one can color $A = G \times H$. Color the vertices $(a,b)$ of $A$ with $g(a,b)=f(a), \; a \in V(G)$. Experimentally the coloring is valid.

This was verified for 1000 random graphs and for $\{ \text{Petersen graph}, K_2,K_6, C_5,\text{Star graph 6} ,\text{Random graph of order 14}, \} \times \\\\ \{\text{All graphs up to 7 vertices}\}$

This is related to Hedetniemi's Conjecture which states $\chi(G \times H) = \min \{ \chi(G), \chi(H) \}$.

1. Any counterexamples to this coloring?
2. Is it possible to prove this is valid coloring for certain $G$ or $H$?
3. What types of graphs are potential counterexamples?

The only way that two vertices $(u,v)$ and $(u',v')$ end up getting the same color is if $f(u)=f(u')$. But then there is no edge between $u$ and $u'$ in $G$ so there is no edge between $(u,v)$ and $(u',v')$ in $G\times H$. So your conjecture is true for all graphs.
In fact, as explained in the page you linked to above, a coloring with $n$ colors is simply a graph homomorphism to $K_n$, the complete graph on $n$ vertices. Since we have a homomorphism $G\times H\to G$ we can simply compose this with a homomorphism $G\to K_n$ whenever $\chi(G)=n$. This gives your construction. It also proves that $\chi(G\times H)\le \min{\chi(G),\chi(H)}$.
• For future users, just adding here that Hedetniemi's Conjecture has been proven false by Yaroslav Shitov, and there exists graphs $G,H$ with $\chi(G\times H)<\min\{\chi(G),\chi(H)\}$. See arxiv.org/abs/1905.02167 Apr 14 '20 at 0:49