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

  • 2
    $\begingroup$ "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. $\endgroup$ – Fedor Petrov Aug 6 at 16:49
  • $\begingroup$ 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? $\endgroup$ – bof Aug 7 at 5:07
  • $\begingroup$ So for instance $K_{2,2}$ has chromatic number $2$ and achromatic number $2$ but it has pseudo-chromatic number $3$, is that right? $\endgroup$ – bof Aug 7 at 5:13
  • $\begingroup$ Unfortunately $\psi(G)$ seems to be a usual notation for the achromatic number of a graph $G$. $\endgroup$ – 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)\}$.

| cite | improve this answer | |
  • 1
    $\begingroup$ Pedantically: $\psi(G\times H)\ge\max\{\psi(G),\psi(H)\}$ assuming each graph has at least one edge. $\endgroup$ – 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$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.