Cómo encontrar el número cromático del $n$ -hipercubo de dimensiones $Q_n$ ?

Question

Cómo encontrar el número cromático el $n$ -hipercubo de dimensiones $Q_n$ ?

Lo sé. $\chi(Q_2)$ =2 , $\chi(Q_3)$ =2 , $\chi(Q_4)$ =4

Answer 1

Todo hipercubo es bipartito (y por tanto el número cromático es siempre 2). Para ver esto, dejemos que $A$ es el conjunto de todas las cadenas que tienen un número impar de 1 bits y $B$ es el conjunto de todas las cadenas que tienen un número par de 1 bits. Dado que dos cadenas son adyacentes si y sólo si difieren exactamente en un bit, se deduce que no puede haber aristas entre dos vértices de $A$ o entre dos vértices de $B$ .

Answer 2

$\chi(Q_4)\ne4$ .

SUGERENCIA: El conjunto de vértices de $Q_n$ es $\{0,1\}^n$ . Para $v=\langle b_1,\dots,b_n\rangle\in\{0,1\}^n$ dejar $c(v)=\left(\sum_{k=1}^nb_k\right)\bmod 2$ .