¡Debes recordar que los vértices diagonales uno del otro pueden ser del mismo color! Su fórmula no tiene eso en cuenta. Podemos encontrar el número cromático de un gráfico a través del principio de inclusión-exclusión. Es una técnica de conteo muy general que nos permite contar estructuras complejas, si podemos probar ciertos límites en ciertos subconjuntos.
La idea principal es que contamos todas las formas posibles en que ocurre una propiedad. Luego eliminamos algunos elementos "malos". Sin embargo, es posible que hayamos eliminado demasiado y necesitemos agregar algunos artículos "buenos". Esto va y viene hasta que hayamos pasado por todos los subconjuntos.
El principio de inclusión-exclusión nos dice que dado un conjunto básico , el número de elementos de que no se encuentran en ninguno de los subconjuntos es
X A i ∑ I ⊆ [ n ] ( - 1 ) | Yo | El | A I | , dónde |X|=nXAi
∑I⊆[n](−1)|I||AI|, where I is the set of indices in X and AI=⋂i∈IAi
Sea el número de colores, y sea el conjunto de todos los colores posibles (es decir, ), y seaλX|X|=λ4
Ae={coloring:e=(i,j)∈E,color(i)=color(j)}
Antes de obtener nuestro polinomio final, necesitamos contar el tamaño de nuestros conjuntos , y el tamaño de todos los subconjuntos que se cruzan.Ae
Observe que . Esto se debe al hecho de que solo coloreamos pero siempre elegimos los mismos colores para los vértices vecinos. En adelante tenemos,|A12|=|A23|=|A34|=|A41|=λ3G
|A12∩A23|=|A23∩A34|=|A34∩A41|=|A41∩A12|=|A12∩A34|=|A41∩A23|=λ2
No voy a enumerar cada conjunto de 3, pero todos tienen el mismo recuento. . Y finalmente, . Ahora recopilemos nuestros términos y sumemos.|Ae∩Ae′∩Ae′′|=λ|A12∩A23∩A34∩A41|=λ
λ4−4λ3+6λ2−4λ+λ=λ4−4λ3+6λ2−3λ
Ahora contar con inclusión-exclusión para este problema no fue tan malo porque teníamos un ciclo simple de 4 ciclos. Si el gráfico tuviera más estructura, rápidamente sería molesto descubrir cada tamaño de intersección para todas las intersecciones posibles.