Fórmula de deleción-contracción

En teoría de grafos , una fórmula de contracción-eliminación/recursión es cualquier fórmula de la siguiente forma recursiva :

${\displaystyle f(G)=f(G\setmenus e)+f(G/e).}$

Aquí G es un grafo, f es una función en grafos, e es cualquier arista de G , G  \  e denota eliminación de arista y G  /  e denota contracción . Tutte se refiere a dicha función como una función W . ^[1] La fórmula a veces se denomina teorema de reducción fundamental . ^[2] En este artículo la abreviamos como DC .

RM Foster ya había observado que el polinomio cromático es una de esas funciones, y Tutte comenzó a descubrir más, incluida una función f  =  t ( G ) que cuenta el número de árboles de expansión de un grafo (véase también el teorema de Kirchhoff ). Más tarde se descubrió que el polinomio de flujo es otro más; y pronto Tutte descubrió una clase completa de funciones llamadas polinomios de Tutte (originalmente denominados dicromatos ) que satisfacen DC. ^[1]

El número de árboles de expansión satisface DC. ^[3]${\displaystyle t(G)}$

Demostración. denota el número de árboles de expansión que no incluyen e , mientras que el número que incluye e . Para ver el segundo, si T es un árbol de expansión de G , entonces contraer e produce otro árbol de expansión de . Por el contrario, si tenemos un árbol de expansión T de , entonces expandir la arista e da dos árboles desconectados; agregar e conecta los dos y da un árbol de expansión de  G . ${\displaystyle t(G\setmenos e)}$${\displaystyle t(G/e)}$$Estilo de visualización G/e$$Estilo de visualización G/e$

Según el teorema de Kirchhoff, la cantidad de árboles de expansión en un grafo se cuenta por un cofactor de la matriz laplaciana . Sin embargo, el polinomio característico laplaciano no satisface la DC. Al estudiar los laplacianos con pesos de vértice, se puede encontrar una relación de contracción-eliminación entre los polinomios característicos laplacianos ponderados por vértice escalados. ^[4]

El polinomio cromático que cuenta el número de k -coloraciones de G no satisface DC, sino una fórmula ligeramente modificada (que puede hacerse equivalente): ^[1]${\displaystyle \chi_{G}(k)}$

${\displaystyle \chi _{G}(k)=\chi _{Ge}(k)-\chi _{G/e}(k).}$

Demostración. Si e = uv , entonces una coloración k de G es la misma que una coloración k de G  \  e donde u y v tienen colores diferentes. Hay coloraciones totales de G  \  e . Ahora necesitamos restar aquellas donde u y v tienen colores similares. Pero tales coloraciones corresponden a las coloraciones k de donde u y v están fusionadas. ${\displaystyle \chi_{G\setminus e}(k)}$$estilo de visualización \chi_{G/e}(k)}$

Esta propiedad anterior se puede utilizar para demostrar que el polinomio cromático es, de hecho, un polinomio en  k . Podemos hacerlo mediante inducción sobre el número de aristas y observando que en el caso base donde no hay aristas, hay coloraciones posibles (que es un polinomio en  k ). ${\displaystyle \chi_{G}(k)}$${\displaystyle k^{|V(G)|}}$

• Principio de inclusión-exclusión
• Polinomio de Tutte
• Polinomio cromático
• Flujo hacia ninguna parte, cero

• Dong, FM; Koh, KM; Teo, KL (junio de 2005). Polinomios cromáticos y cromaticidad de gráficos . World Scientific. doi :10.1142/5814. ISBN 978-981-256-317-0.