Let $G=(V,E)$ be a finite simple graph. We say a map $p:V\to [n]:=\{1,\ldots,n\}$ is a *pseudo-coloring* if for all $a\neq b\in[n]$ there is $v\in\psi^{-1}(\{a\})$ and $w\in\psi^{-1}(\{b\})$ such that $\{v,w\}\in E$. We denote the maximal number $m$ such that there is a pseudo-coloring $p:V\to [m]$ by $\psi(V)$.


An easy argument shows that every coloring in the traditional sense is also a pseudo-coloring, which implies that $\psi(G) \geq \chi(G)$.


Let $G, H$ be finite simple undirected graphs.
Do we necessarily have $$\psi(G\times H) \leq \min\{\psi(G),\psi(H)\}?$$


(By $G\times H$ we denote the categorical product, sometimes also referred to as the [tensor product of graphs](https://en.wikipedia.org/wiki/Tensor_product_of_graphs).)



Hedetniemi for pseudo-chromatic number $\psi(G)$
It is not true. Let $G$ and $H$ be graphs, and let $p\_{max}$ be maximal pseudo-coloring of the graph $H$. Show that the map $p((x,y))=p\_{max}(y)$ is pseudo-coloring of graph $G\times H$. Fix some $\{u,v\}\in E(G)$. For arbitrary distinct colors $a,b$ there exist $\{k,l\}\in E(H)$ such that $p\_{max}(k)=a$ and $p\_{max}(l)=b$. Then the edge $\{(u,k),(v,l)\}$ connects colors $a$ and $b$ in $G\times H$. Hence $\psi(G\times H)\geq \max\{\psi(G),\psi(H)\}$.


