Chromatic Polynomial: Counting Colorings via Graph Recurrences

Learn to compute and reason about the chromatic polynomial $X_G(k)$ so you can count proper colorings for any number of colors at once, use deletion–contraction confidently, read structural information from coefficients, and connect coloring counts to deeper invariants like the Tutte polynomial.

A graph can be 3-colorable and still have wildly different numbers of 3-colorings. The chromatic polynomial captures that whole counting profile in one object: a single polynomial $X_G(x)$ whose value at $x=k$ is the number of proper $k$-colorings. That makes it strictly richer than the chromatic number, which only tells you the smallest $k$ where the count becomes nonzero. See how one fixed graph gives different counts at $k=2,3,4$ while still fitting one formula.

Conventions that change what gets counted

A proper coloring is a function from vertices to a set of $k$ labeled colors, with adjacent vertices forced to be different. Labeled matters: swapping red and blue counts as a different coloring unless you explicitly decide otherwise. Likewise, vertices are treated as distinct even if the drawing suggests symmetry.

Two common conventions keep computations sane:

• Work with simple graphs unless told otherwise, meaning no loops and no parallel edges.
• When loops or multiedges appear during contraction, interpret them in the coloring constraint sense, not as new combinatorics.

A loop makes proper coloring impossible because a vertex would need to differ from itself, so the count is $0$ for every $k$. Parallel edges do not add a new restriction beyond adjacency, so multiple copies behave like one edge for colorings. Disconnected graphs factor, because you can color components independently and multiply the counts.

Explore how these edge cases behave under the definition.

Counting lens
Always ask what constraint set you are counting under. Chromatic polynomials count label-distinct colorings under adjacency constraints, not colorings up to symmetry.

Deletion–contraction, the recurrence you actually use

For an edge $e$ of $G$, the chromatic polynomial satisfies

$$X_G(x)=X_{G-e}(x)-X_{G/e}(x).$$

Here $G-e$ deletes the edge, and $G/e$ contracts it by identifying its endpoints and keeping any induced adjacencies.

Why the subtraction. Count proper $k$-colorings of $G-e$ and split them into two disjoint types: those where the endpoints of $e$ get different colors, and those where they get the same color. The different-color type is exactly the proper $k$-colorings of $G$, because adding back $e$ does not break anything. The same-color type is exactly the proper $k$-colorings of $G/e$, because identifying equal-colored endpoints is consistent with the rest of the coloring. So for each integer $k$, $X_{G-e}(k)=X_G(k)+X_{G/e}(k)$, giving the polynomial identity above.

Base cases are what stop the recursion:

• If $G$ has no edges and $n$ vertices, then $X_G(x)=x^n$.
• If a loop appears, the polynomial is $0$.

The recurrence is less about brute force and more about choosing an edge that produces graphs you can recognize quickly.

Watch how one highlighted edge drives the split into the two cases.

Closed forms you should memorize

You can compute any $X_G(x)$ by deletion–contraction, but several families appear so often that it is faster to recognize them. Paths and trees behave the same because you can color one vertex freely, then each new vertex has exactly one forbidden color along the edge you add.

A small set of patterns covers a lot of homework and exam graphs:

• Complete graphs force all vertices different.
• Trees have the clean multiplicative step-by-step count.
• Cycles are like paths, except the last vertex must also avoid the first, introducing a correction term.

Compare the standard families and their formulas.

One useful habit is to sanity-check a closed form at small $k$. If a graph has an edge, $X_G(1)=0$ must hold. If it has a triangle, $X_G(2)=0$ must hold. Those checks catch most algebra slips.

Fast check
Plug in $x=0,1,2$ mentally. Many graphs force zeros there, and the chromatic polynomial must respect them.

What coefficients know about the graph

For a graph on $n$ vertices, $X_G(x)$ has degree $n$ and leading coefficient $1$. That is not cosmetic. It reflects that for large $k$ you can almost choose colors independently, and the first correction comes from edges forbidding equalities.

Several coefficients have direct structural meaning:

• The coefficient of $x^{n-1}$ is $-|E|$, the negative number of edges.
• Coefficients alternate in sign for simple graphs.
• If $G$ has $c$ connected components, then the lowest nonzero term is $x^c$. In particular, $x^0,x^1,\dots,x^{c-1}$ have coefficient $0$.

You can read these as consistency conditions when you compute by recursion. If your final polynomial is not monic of degree $n$, something went wrong. If the $x^{n-1}$ coefficient does not match the edge count, you likely mis-handled a contraction that created a loop or you dropped a vertex count.

See how the polynomial can be annotated to point back to vertices, edges, and components.

Subset expansion and the Tutte connection

Deletion–contraction is operational, but there is also a global formula:

$$X_G(x)=\sum_{S\subseteq E}(-1)^{|S|}x^{c(G(S))},$$

where $G(S)$ is the spanning subgraph with edge set $S$ and $c(G(S))$ is its number of connected components. This is inclusion–exclusion in disguise: each chosen edge in $S$ enforces an equality constraint between its endpoints, and the sign tracks how many constraints you impose.

The conceptual payoff is that $X_G$ is not an isolated trick. It is a specialization of the Tutte polynomial $T_G(x,y)$ via $X_G(x)=T_G(x,0)$. That explains why deletion–contraction keeps showing up, and why so many evaluations of these polynomials count seemingly unrelated objects.

Open the optional deep dive when you want the subset-sum view spelled out.

Using chromatic polynomials beyond textbook coloring

Vertex coloring is a constraint model. If tasks cannot share a resource, put an edge between them and a proper coloring is a feasible assignment of $k$ resources. The chromatic polynomial then counts how many feasible assignments exist, not just whether one exists.

A few evaluations are especially striking:

• $X_G(k)$ for small $k$ tells you how tight the constraints are. Two graphs can both be 3-colorable, but one may have very few 3-colorings.
• $X_G(-1)=(-1)^{|V|}\cdot a(G)$ where $a(G)$ is the number of acyclic orientations of $G$. A polynomial built from colorings unexpectedly counts directed acyclic structure at a negative input.

Software can compute $X_G(x)$ by deletion–contraction, but the recursion tree can explode since counting colorings is #P-hard in general. That makes good modeling and simplification choices matter even when you hand the computation off to a tool.

Try mapping a real constraint scenario to a graph and picking a computation approach.

Choose edges that shrink the recursion

Deletion–contraction is only painful when you pick edges that do not simplify the graph. The best edge is one that makes one branch trivial and the other recognizable.

Heuristics that usually help in hand computations:

• Prefer an edge on a cycle. Deleting it often breaks the cycle into a tree-like piece, which you can do quickly.
• Prefer an edge whose contraction creates a loop or obvious simplification. A loop immediately zeroes that branch.
• Exploit separations. If deletion makes the graph disconnected, you can factor the polynomial into a product on components.
• Keep vertex counts straight. Contraction reduces the vertex count by one, and losing track is the most common algebra mistake.

When a computation feels stuck, it is often because you are aiming for a fully expanded polynomial too early. Sometimes it is cleaner to keep expressions factored in terms like $x(x-1)^{n-1}$ until the end, especially if you only care about values at specific $k$.