Autor Tema: Coloreo de grafos.

0 Usuarios y 1 Visitante están viendo este tema.

16 Marzo, 2020, 06:03 pm
Leído 840 veces

murkillerx

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 26
  • Karma: +0/-0
  • Sexo: Masculino
Necesito ayuda con un ejercicio sobre     Título corregido

El "queen graph"  \(  Q_n  \) es el grafo cuyos vértices son los  \(  n^2  \) casilleros de un tablero cuadrado con  \(  n  \) filas y  \(  n  \) columnas. Dos vértices son vecinos si poniendo una reina de ajedrez en cada uno de los casilleros las reinas se atacan mutuamente. (es decir, si los casilleros están en una misma fila, columna o diagonal, donde diagonal no es necesariamente una de las diagonales principales).
Probar que si  \(  n  \) es coprimo con 6, entonces  \(  \varkappa(G) = n  \).

Lo que tengo hasta ahora es que dado que todos los casilleros de una misma fila, una misma columna o una misma diagonal son vecinos entre sí, el grafo completo \(  K_n  \) está incluido en \(  Q_n  \) por lo que \(  \varkappa(G) >= n  \). Ahora bien, desconozco alguna cota superior lo suficientemente cercana a \(  n  \).

17 Marzo, 2020, 01:43 pm
Respuesta #1

geómetracat

  • Moderador Global
  • Mensajes: 1,905
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
La ecuación más bonita de las matemáticas: \( d^2=0 \)

18 Marzo, 2020, 06:56 am
Respuesta #2

murkillerx

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 26
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias me sirvio bastante.