$n$-Gráfico de partita formado por $\{0,1,2, \dots, n-1\}^k$

Question

Hay muchas preguntas sobre cómo un gráfico $Q_k$y también se conoce como k-cube y es bipartito. Donde un$Q_k$ cuyos vértices están etiquetados por cadenas de longitud $k$ encima $\{0, 1\}$. Hay un borde entre los vértices si las cadenas que los etiquetan difieren exactamente en un lugar.

Ahora, ¿qué cambiaría si este gráfico, $Q_k$ y estaba formado por $n$-cargas de longitud $k$. Y hay un borde entre los vértices si las cadenas que los etiquetan difieren exactamente en un lugar. ¿Cómo sería un gráfico así?$n$-partita?

Answer 1

Creo que la siguiente coloración demuestra que $3$ los colores son suficientes (es decir, que dicho gráfico es tripartito): Dada una cadena $s \in \{0, 1, 2 \}^k$ denotamos por $f(s)$ la suma de los dígitos de $s$. Definimos nuestra coloración como la función$C$ que mapas $s$ a la suma de sus dígitos módulo $3$, es decir $C : s \rightarrow \mathcal{R}_3(f(s))$.

Considere dos cadenas adyacentes $s$ y $s'$. Se diferencian exactamente en una posición. Sin pérdida de generalidad tenemos$f(s) < f(s') < f(s) + 3$. Por lo tanto$\mathcal{R}_3(f(s)) \neq \mathcal{R}_3(f(s'))$ y por lo tanto $s$ y $s'$debe tener un color diferente. Esto prueba que$C$ es una coloración adecuada.

Observe que hay un argumento subyacente general: para $l$-ary cadenas, podría probar que se pueden colorear usando $l$ colores de la misma manera.