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](http://garden.irmacs.sfu.ca/?q=op/hedetniemis_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?



Coloring tensor products of graphs
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)}$.


