Chromatic Polynomial

Menge an Partitionen von $V(G)$ in $n$ non-empty Independent Set.

$${\mathcal{V}}_{n-1}(G)=\left(\genfrac{}{}{0ex}{}{n}{2}\right)-|E(G)|$$ $${\mathcal{V}}_n(G)=1$$

Menge an vertex colorings

$$P(G,t)=\sum _{k\ge 1}{\mathcal{V}}_k(G)t(t-1)...(t-k+1)$$ $$P(K_n,t)=t(t-1)...(t-k+1)$$ $$P(N_n,t)=t^n$$ $$P(T,t)=t(t-1{)}^{n-1}$$

Deletion contraction forumlar

Chromatic number of planar graphs