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

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

• "every coloring in the traditional sense is also a pseudo-coloring" - why so? I see it only for colorings in the minimal number of colors. – Fedor Petrov Aug 6 at 16:49
• If I understand correctly, the difference between the pseudo-chromatic number and the achromatic number is that a pseudo-coloring is not required to be a proper coloring, i.e., adjacent vertices may have the same color. Have I got that right? – bof Aug 7 at 5:07
• So for instance $K_{2,2}$ has chromatic number $2$ and achromatic number $2$ but it has pseudo-chromatic number $3$, is that right? – bof Aug 7 at 5:13
• Unfortunately $\psi(G)$ seems to be a usual notation for the achromatic number of a graph $G$. – bof Aug 7 at 8:00

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)\}$$.
• Pedantically: $\psi(G\times H)\ge\max\{\psi(G),\psi(H)\}$ assuming each graph has at least one edge. – bof Aug 7 at 6:18
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$$.