Cromática número de generalizada hipercubo

Question

Es claro que la cromática número de $Q_n$$2$. Pero, ¿qué acerca de la gráfica de $G$ con conjunto de vértices ${n}^{(r)}$ donde dos vértices son adyacentes si y sólo si sus coordiantes difieren por uno?

Parece que no puede encontrar cualquier tipo de buena coloración a todos aquí.

Answer 1

La cromática número es $n.$

De hecho, consideran que los vértices se $r$-tuplas de $\{1,\ldots,n\}.$ Colorear los vértices $v = (v_1,\ldots,v_r)$ con 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.$

Para ver que la cromática número es al menos $n$ nota de que, dado los elementos fijos $v_1,\ldots,v_{n-1}$ el conjunto $\{ (v_1,\ldots,v_{n-1},k) \mid k \in \{1,\ldots,n\}\}$ induce una $n$-clique en $G.$

Otra forma más directa de ver esto es que sus gráficos son los productos cartesianos de $K_n$ $G_r = \square_{i=1}^r K_n$ y una identidad bien conocida dice $$\chi(G \square H) = \rm{max}(\chi(G), \chi(H)).$$