Where $\chi(G)$ denotes the chromatic number, $\overline{G}$ the graph complement, and $\times$ the Cartesian Graph Product:
I need to show that $(\forall G,H)( \chi(\overline{G \times H}) \leq \chi(\overline{G}) \cdot \chi(\overline{H}))$. This is a stepping stone in a proof I am writing, but I am having difficulty showing this.
It would be good if I could show that $\chi(\overline{G \times H}) \leq \chi(\overline{G}) \cdot \chi(\overline{H})$ is equivalent to $\chi(G \times H) \leq \chi(G) \cdot \chi(H)$, as it is a known result (Sabidussi 1957) that $\chi(G \times H) = \max \{ \chi(G),\chi(H)\}$. However, I am not sure if those two cases are really equivalent.
Specifically, I am not sure if it holds for all $G,H$ that $\overline{G} \times \overline{H} = \overline{G \times H}$.
Any help?
The OP probably means the tensor product. The only 'categorical' product for graphs is the tensor product. That is why most people reserve "$\times$" for the tensor product. The cartesian product is commonly indicated with "$\square$". In both the cartesian product and the tensor product the vertex set is the cartesian product of the individual vertex sets (which may have caused the confusion), but adjacencies are defined differently.
In $\overline{G\times H}$ (complement of tensor product) adjacency is defined by $(g,h)\sim(g',h')$ if and only of $g\nsim g'$ or $h\nsim h'$. Now let $c$ be a proper coloring of $\overline{G}$ and $d$ a proper coloring of $\overline{H}$. Then $c\times d:(g,h)\mapsto(c(g),d(h))$ is a proper coloring of $\overline{G\times H}$ with $\chi(\overline{G})\times\chi(\overline{H})$ colors.
Indeed: if $(g,h)\sim(g',h')$ then $g\nsim g'$ or $h\nsim h'$, so $g\sim g'$ in $\overline{G}$ or $h\sim h'$ in $\overline{H}$, which means that either $c(g)$ and $c(g')$ are different, or $d(h)$ and $d(h')$ are different.