Hedetniemi for pseudo-chromatic number $\psi(G)$

Question

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.)

Answer 1

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)\}$.

Answer 2

Here is a very simple example for $\psi(G\times H)\gt\max\{\psi(G),\psi(H)\}$.

The graph $G=H=K_3$ has achromatic number and pseudo-chromatic number equal to $3$. The tensor product $K_3\times K_3$ has achromatic number and pseudo-chromatic number $5$, as shown by the following coloring: assuming $V(K_3)=[3]$, define $p(1,1)=p(1,2)=1$, $p(1,3)=p(2,3)=2$, $p(3,3)=p(3,2)=3$, $p(3,1)=p(2,1)=4$, $p(2,2)=5$.