Número cromático de un gráfico en un tablero de ajedrez

Question

Para una pieza de ajedrez Q, el gráfico Q es el grafo cuyos vértices son las casillas del tablero de ajedrez y las dos casillas son adyacentes si Q puede pasar de una de ellas a la otra en un solo movimiento. Encuentra el número cromático del gráfico Q cuando Q es (a) el rey, (b) una torre (c) un alfil, (d) un caballo.

Así que mi primera idea sería pensar en cada movimiento distinto que podría hacer una pieza si estuviera en el centro del tablero, ya que éste sería el grado máximo de todos los vértices del gráfico y, por tanto, el mayor número de vecinos que podría tener un gráfico que mostrara cuántos colores distintos se necesitan?

Answer 1

Dentro de un $2\times 2$ casilla, el rey puede pasar de cualquiera directamente a cualquier otro campo, por lo que necesitamos al menos cuatro colores. Si asignamos el color $(x\bmod 2, y\bmod 2)$ al campo $(x,y)$ , ew ver que $4$ los colores también son suficientes.

En el caso de la torre, todos los campos de una columna son adyacentes entre sí y, por tanto, deben tener colores diferentes, por lo que se requiere al menos $8$ colores. Pero ocho colores también son suficientes si se asignan $x+y\bmod 8$ a $(x,y)$ .

Del mismo modo, el alfil tiene campos adyacentes a lo largo de una diagonal, por lo que también requiere ocho colores. Pero ocho colores también son suficientes asignando el color $x$ a $(x,y)$ .

Para el caballo, la coloración original del tablero es testigo de que el número cromático es 42$.

Answer 2

(a) El rey conecta $4$ cuadrados, por lo que el número cromático es al menos $4$ . Si coloreamos las casillas según la paridad del rango y la paridad de la fila, el rey no puede mantener ambas paridades iguales; así que el número cromático es $4$ .

(b) Una torre conecta todas $8$ cuadrados en una fila o expediente, por lo que el número cromático es al menos $8$ . Si cada cuadrado está coloreado por el residuo de la suma del rango y el archivo módulo $8$ la torre no puede permanecer en el mismo residuo, por lo que el número cromático es $8$ .

(c) Un alfil en la diagonal larga conecta $8$ cuadrados, por lo que de nuevo el número cromático es al menos $8$ . El alfil no puede permanecer en el mismo rango o fila, por lo que podemos colorear las casillas según su rango o fila; así el número cromático vuelve a ser $8$ .

(d) ya se ha resuelto en los comentarios: Se puede colorear cada casilla con el color que tiene en el tablero, por lo que el número cromático es $2$ .