Deletion-contraction
P(G, k) = P(G-e, k) - P(G/e, k). Take any edge, either don't use it (delete) or force endpoints same color (contract).
Advertisement
Base cases
Empty graph on n vertices: k^n. Tree on n: k(k-1)^(n-1). Complete graph K_n: k(k-1)(k-2)…(k-n+1).
Advertisement
Complexity
Exponential in general (#P-hard). Polynomial only for structured graphs.
Special values
P(G, 1) = 0 for any graph with edge. P(G, k) = 0 iff chromatic number > k.