Chromatic Polynomial

P(G,k) = number of proper k-colorings — deletion-contraction algorithm

Graph editor — click: add vertex | click two vertices: add/remove edge

Chromatic Polynomial P(G,k)

—

Evaluate at k = 3

P(G, 3) = —

χ(G) = chromatic number: —
|V| = 0 |E| = 0

P(G,k) vs k curve

Coloring (k colors applied)

Deletion-contraction: P(G,k) = P(G−e,k) − P(G/e,k) for any edge e.
Base cases: P(empty,k) = k^n, P(K_n,k) = k(k−1)…(k−n+1).
Properties: P(G,0)=0; leading term k^n; coefficients alternate in sign.
Roots of P(G,k) are the "chromatic roots" — related to the Tutte polynomial.