Graph Coloring — Chromatic Polynomial via Deletion-Contraction

Graph Builder

Click to add nodes. Click two nodes to add edge. Right-click to remove.

k colors available: 4

Chromatic number χ(G)—

P(G,k) for k=4—

Edges0

Current coloring valid—

Chromatic Polynomial P(G,k)

—

Theory

The chromatic polynomial P(G,k) counts the number of proper k-colorings. The deletion–contraction formula: P(G,k) = P(G-e, k) − P(G/e, k) for any edge e. Base cases: P(empty on n vertices, k) = kⁿ.

Coefficients alternate in sign. Roots of P(G,k) are always real (Chordal graphs). The chromatic number χ(G) = smallest k with P(G,k) > 0. For planar graphs, χ≤4 (Four Color Theorem). The complexity of computing P(G,k) is #P-hard.

Graph Coloring — Chromatic Polynomial via Deletion–Contraction

Graph Builder

Chromatic Polynomial P(G,k)

Theory