Halla el polinomio cromático de la siguiente gráfica

Question

http://i.imgur.com/TwOy3sk.png

Conozco el método de contracción de los bordes, pero después de probarlo en este problema parece que va a tardar demasiado.

Así que voy a tratar de resolver esto directamente, pero no estoy muy cómodo con este método, esto es lo que tengo hasta ahora.

1 tiene x opciones. 2 tiene (x-1) opciones, 4 tiene (x-2) opciones, 3 tiene (x-2) opciones, 5 tiene (x-1) opciones, 7 tiene (x-2) opciones y 6 tiene (x-2) opciones, lo que nos da

Pg(x) = x(x-1)^2(x-2)^4.

¿Es esto correcto?

Observa que "1" es el vértice más a la izquierda, "2 y 3" son los vértices adyacentes a "1", y así sucesivamente.

Answer 1

Intenta demostrar lo siguiente:

Denotemos $G$ un gráfico que se construye "pegando" gráficos $K$ y $H$ por un vértice común (como en tu imagen). Tenemos que $P_G(x)=\frac{P_K(x)P_H(x)}{x}$

Answer 2

Creo que empezar por el vértice del medio es lo mejor, aunque sólo sea por la simetría del problema.

Supongamos que $x\geq 3$ . En el vértice central, tienes $x$ elección del color. Entonces el vértice superior izquierdo y el vértice superior derecho tienen cada uno $x-1$ elección. Entonces, el vértice inferior izquierdo y el inferior derecho tienen cada uno $x-2$ elección. Entonces el más a la izquierda y el más a la derecha tienen $x-2$ elección. Esto nos deja con $x(x-1)^{2}(x-2)^{4}$ . Puede comprobar fácilmente que este trabajo para $x=1,2$ también.

Se obtiene la misma respuesta de cualquier manera.