Polinomio cromático del gráfico de escalera

Question

Hola chicos estoy tratando de entender la fórmula del polinomio cromático de un gráfico de escalera.

$$k(k-1)(k^2-3k+3)^{n-1}$$

¿Pueden ayudarme a entender cómo llegamos a esto?

Answer 1

Utilice la supresión-contracción como se describe en este Entrada de Wikipedia . Que la arista de eliminación $(u,v)$ sea la arista de la parte superior de la escalera y que $G_n$ sea el gráfico de la escalera. Entonces tenemos $$P(G_n,k) = P(G_n-uv,k)-P(G_n/uv,k).$$ Pero $G_n-uv$ es un gráfico de escalera de altura $n-1$ con dos vértices libres en la parte superior. Cada uno de ellos puede tomar cualquiera de $k-1$ colores, ya que sólo tienen que diferir en el color del vértice en el que se unen a la escalera y no hay ningún borde entre ellos. Por lo tanto, $$P(G_n-uv,k) = (k-1)^2 P(G_{n-1},k).$$ El gráfico $G_n/uv$ tiene un vértice unido a los dos vértices superiores para formar un triángulo. Este vértice debe diferir en color de los dos vértices donde está unido a la escalera. Por lo tanto, $$P(G_n/uv,k) = (k-2) P(G_{n-1},k).$$ Concluimos que $$P(G_n,k) = ((k-1)^2 - (k-2)) P(G_{n-1},k) = (k^2-3k+3) P(G_{n-1},k).$$ Ahora sólo hay que utilizar el hecho de que el gráfico de escalera de altura uno es un camino en dos vértices y tiene $k(k-1)$ colores.

Answer 2

Ver aquí http://exwiki.org/mw/index.php?title=The_chromatic_polynomial_of_the_ladder_graph

La idea es utilizar el hecho de que si $G$ tiene subgrafos $H_1,H_2$ tal que $H_1 \cup H_2 = G$ y $H_1 \cap H_2 = K_n$ puis $$P(G,k) = \frac{(H_1,k)P(H_2,k)}{P(K_n,k)}$$

Esto se puede utilizar para hacer una recurrencia directa para $P(L_n,k)$

Answer 3

Podemos hacerlo de forma inductiva. cuando $n=1$ esto es sólo $K_2$ por lo que la fórmula se mantiene claramente. Entonces supongamos que se cumple para $n-1$ y demostrar que para $n$ la fórmula es $P(G_n,k)=(k^2-3k+3)*P(G_{n-1},k)$ . Nombra los dos puntos añadidos como $u,v$ respectivamente. Entonces, por contracción de borrado, $P(G_n,k)=P(G_n-uv,k)-P(G_n/uv)$ en el primero de estos nuevos polinomios, es el mismo que $G_{n-1}$ con dos vértices colgantes añadidos; estos pueden ser de un solo color, el de su adyacencia. En el segundo tenemos ahora un punto añadido en $G_{n-1}$ . Esto puede ser todo menos dos colores. Entonces tenemos $P(G_{n-1},k)((k-1)^2-(k-2))=P(G_{n-1},k)(k^2-3k+3)$ . Entonces, inductivamente, la fórmula se mantiene.

Answer 4

Toma el punto del extremo inferior izquierdo y empieza a colorear desde ahí. hay k opciones para ese color (supongamos que lo coloreamos con el color a). Ahora ve al de abajo a la derecha, hay k-1 opciones para el color de ese elemento(supongamos que lo coloreamos con el color b). ¿Cuántos pares hay disponibles para los dos vértices anteriores?

una opción es tomar la de la izquierda con a y la de la derecha con b.(1 vía)

la otra es colorear el de la izquierda con b y el de la derecha con un color diferente a a o al de la izquierda: ( $k-2$ formas)

otra es colorear el de la derecha con a y el de la izquierda con un color diferente a b ( $k-2$ opciones)

y la última opción es colorear los de arriba con colores diferentes a los de arriba $(k-2)(k-3)=k^2-5k+6$

sumándolos todos para obtener $k^2-3k+3$ formas de colorear cada par de arriba.

utilizando que hay n-2 pares de este tipo y el principio fundamental de conteo y el hecho de que hay k opciones para la parte inferior izquierda y k-1 para la parte inferior derecha sabemos que hay $k(k-1)(k^2-3k+3)^{n-1}$ colorantes al gusto.