Chromatic number of generalized hypercube

Question

It's clear that the chromatic number of $Q_n$ is $2$. But what about the graph $G$ with vertex set ${n}^{(r)}$ where two vertices are adjacent if and only if their coordiantes differ by one?

Can't seem to find any sort of good colouring at all here.

Answer 1

The chromatic number is $n.$

Indeed, consider that the vertices are $r$-tuples from $\{1,\ldots,n\}.$ Coloring the vertex $v = (v_1,\ldots,v_r)$ with color $$c(v) = \sum_{i=1}^r v_i \pmod{n},$$ gives you a proper coloring. For if $$v = (v_1,\ldots,v_{i-1},x,v_{i+1},\ldots,v_{r}) \quad \mbox{and} \quad v' = (v_1,\ldots,v_{i-1},y,v_{i+1},\ldots,v_{r})$$ are two distinct adjacent vertices then $v$ receives the color $$c(v) = c(v') - x + y \pmod{n} \ne c(v')$$ since $x,y \leq n.$

To see that the chromatic number is at least $n$ note that given fixed elements $v_1,\ldots,v_{n-1}$ the set $\{ (v_1,\ldots,v_{n-1},k) \mid k \in \{1,\ldots,n\}\}$ induces a $n$-clique in $G.$

Another more direct way to see this is that your graphs are the cartesian products of $K_n$ that is $G_r = \square_{i=1}^r K_n$ and a well known identity says $$\chi(G \square H) = \rm{max}(\chi(G), \chi(H)).$$