5
$\begingroup$

Let $G, H$ be two infinite connected graphs. Suppose that we can color $G$ and $H$ in $m$ and $n$ colors respectively so that monochromatic clusters (i.e. monochromatic connected components) are of uniformly bounded diameters. Is it possible to color the Cartesian product $G\times H$ in $m+n-1$ colors so that the diameters of monochromatic clusters are bounded. Here $G \times H$ is the graph with vertices $(x,y), x\in G, y\in H$ and $(x,y)$ connected with $(p,q)$ iff either $x=p$ and $y,q$ are adjacent in $H$ or $y=q$ and $x,p$ are adjacent in $G$.

Example. Let $Z_3$ be the graph with vertices $i\in \mathbb{Z}$ and edges $(i,j)$ where $|i-j|\le 3$. It can be colored in 2 colors as follows: color intervals $[10k+1, 10k+5]$, $k\in \mathbb{Z}$, in black and intervals $[10k+6,10(k+1)]$ in white. All monochromatic clusters have diameters 2. Then $Z_3\times Z_3$ can be colored in 3=2+2-1 colors so that all monochromatic clusters have uniformly bounded diameters. The clusters are bricks.

Update The question above turned out to be too easy and not what I wanted to ask. Here is the real question.

Let $G, H$ be two infinite connected graphs. Pick a number $\lambda\ge 1$. Suppose that we can color $G$ and $H$ in $m$ and $n$ colors respectively so that monochromatic $\lambda$-clusters (i.e. maximal subsets $X$ where any two vertices $u,v$ are connected by a monochromatic sequence $u=x_0, x_1, ..., x_k=v$ where the distance between $x_i, x_{i+1}$ is at most $\lambda$) are of uniformly bounded diameters. Is it possible to color the Cartesian product $G\times H$ in $m+n-1$ colors so that the diameters of monochromatic $\lambda$-clusters are bounded. Here $G \times H$ is the graph with vertices $(x,y), x\in G, y\in H$ and $(x,y)$ connected with $(p,q)$ iff either $x=p$ and $y,q$ are adjacent in $H$ or $y=q$ and $x,p$ are adjacent in $G$.

In the first version of the question $\lambda=1$. For an example, consider the graph $\mathbb{Z}$ (a line), and $\lambda=3$.

$\endgroup$
2
  • $\begingroup$ If David's answer worked before (of which I am unsure), should it not also work here, as to get to a different cluster of the same color one needs lambda + 1 steps "in both directions"? Gerhard "Still Worried At First Version" Paseman, 2012.06.18 $\endgroup$ Jun 18, 2012 at 22:55
  • $\begingroup$ David's proof does not work for $\lambda=2$ even for $G=H=\mathbb{Z}$ because you can switch directions. A fancier reason is that the asymptotic dimension of the plane is 2, so you need 3 colors for almost all $\lambda$. The question asks if the dimension of direct product at scale $\lambda$ is the sum of dimensions of the factors. $\endgroup$
    – user6976
    Jun 19, 2012 at 4:01

1 Answer 1

5
$\begingroup$

Yes. In fact you only need max$(m, n)$ colors. Let's assume $m \leq n$ (switching $G$ and $H$ if necessary.) Number the colors from 0 to $m - 1$ and 0 to $n - 1$. If $x$ has color $i$ and $y$ has color $j$, then give $(x, y)$ color $i + j$ mod $n$. Then the monochromatic connected components of the cartesian product are the cartesian products of the monochromatic connected components.

$\endgroup$
1
  • $\begingroup$ Thank you! You are right! I made the question too easy. I will add an update. $\endgroup$
    – user6976
    Jun 18, 2012 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.