Colorear puntos de un n-gon

Question

Dado un $n$ -¿cuántas maneras puedes colorear los vértices utilizando $k$ colores para que no haya dos vértices adyacentes del mismo color?

(Inspirado en 2011 AMC 12 A # 16 - Soy capaz de hacer esto para los casos pequeños, pero no en general).

Answer 1

He aquí dos formas de resolver el problema, ambas basadas en la teoría de grafos. El problema es equivalente a contar el número de paseos cerrados de longitud $n$ en el grafo completo $K_k$ en $k$ vértices. El número de paseos cerrados de longitud $n$ en un gráfico $G$ con matriz de adyacencia $A$ viene dada por $\text{tr } A^n = \sum_{i=1}^k \lambda_i^n$ donde $\lambda_i$ son los valores propios de $A$ .

Por tanto, basta con calcular los valores propios de la matriz de adyacencia de $K_k$ . Este es un bonito ejercicio, pero en aras de la exhaustividad le diré que son $k-1, -1, -1, ...$ . Así que la respuesta final es

$$(k-1)^n + (k-1)(-1)^n.$$

---

El segundo método consiste en observar que el problema equivale a calcular el polinomio cromático del grafo cíclico $C_n$ . Esto puede hacerse por inducción y la recurrencia de deleción-contracción y obtendrá la misma respuesta.

---

Obsérvese que estas dos soluciones se generalizan en direcciones diferentes. La primera solución sugiere una generalización del problema en la que se sustituye $K_k$ con un gráfico más complicado, mientras que la segunda solución propone una generalización del problema en la que se sustituye $C_n$ con un gráfico más complicado. Ambos problemas son a su vez casos especiales del siguiente problema.

Definición: Sea $G, H$ dos grafos (simples, no dirigidos). A morfismo $f : G \to H$ es una función $f : V_G \to V_H$ enviando vértices de $G$ a los vértices de $H$ tal que, si $u, v \in G$ están conectadas por una arista, entonces $f(u), f(v)$ también están conectadas por una arista.

Problema: Cuántos morfismos hay a partir de un grafo dado $G$ a un gráfico dado $H$ ?

El problema del paseo corresponde a dejar que $G = C_n$ y dejando $H$ sea arbitraria, mientras que el problema de coloreado corresponde a dejar que $H = K_k$ y dejando $G$ sea arbitraria. Ambos son casos muy especiales. El problema general es interesante; no tengo ni idea de lo que se sabe al respecto.

Answer 2

¿Conoces el polinomio cromático? Tiene una fórmula sencilla que puede calcularse fácilmente para n-gons. Es un polinomio en k, el número de coloraciones posibles.