1
$\begingroup$

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

$\endgroup$
4
  • 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$ Aug 6 '20 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 '20 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 '20 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 '20 at 8:00
4
$\begingroup$

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

$\endgroup$
1
  • 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 '20 at 6:18
3
$\begingroup$

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

$\endgroup$

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.