The Chromatic Polynomial — Mathematics Knowledge System

Overview

The chromatic polynomial P(G, k) counts the number of ways to properly color the vertices of a graph G using at most k colors, where 'proper' means no two adjacent vertices share a color. Introduced by George Birkhoff in 1912 as a tool to attack the Four Color Theorem, it turns graph coloring — normally a yes/no existence question ('can this map be colored with 4 colors?') — into a counting question whose answer is always an honest polynomial in k. Plugging in k = 4 and checking whether P(G, 4) > 0 tells you whether G is 4-colorable; the polynomial's degree, leading coefficient, and sign pattern also encode structural facts like the number of vertices and edges of G.

Intuition

Imagine coloring vertices one at a time and counting your choices at each step. For a tree, pick any vertex as a root and color it freely: k choices. Every other vertex has exactly one already-colored neighbor (its parent), so it just needs to avoid that one color: k − 1 choices each, for the remaining n − 1 vertices — giving k(k−1)^(n−1) with no further constraints, because a tree has no cycles to create conflicts between non-adjacent choices. Cycles are harder precisely because the 'last' vertex you color has TWO already-colored neighbors (its two cycle-neighbors), which is exactly why the cycle formula needs the extra (−1)^n correction term instead of the tree's clean product.

Formal Definition

Definition

P(G, k) is the number of proper k-colorings of G. It satisfies the deletion-contraction recurrence and has known closed forms for standard graph families:

P(G, k) = P(G - e, k) - P(G / e, k)

Deletion–contraction recurrence for any edge e

P(K_n, k) = k(k-1)(k-2)\cdots(k-n+1)

Complete graph K_n (falling factorial)

P(T, k) = k(k-1)^{\,n-1} \quad \text{for any tree } T \text{ on } n \text{ vertices}

Trees

P(C_n, k) = (k-1)^n + (-1)^n (k-1)

Cycle graph C_n

Worked Examples

For K_n, the chromatic polynomial is the falling factorial k(k-1)(k-2)...(k-n+1); here n=4.
$P(K_4, k) = k(k-1)(k-2)(k-3)$
Evaluate at k=3: one of the four factors is (k-3)=0.
$P(K_4, 3) = 3\cdot 2\cdot 1\cdot 0 = 0$
Evaluate at k=4.
$P(K_4, 4) = 4\cdot 3\cdot 2\cdot 1 = 24$

Answer: P(K4,k) = k(k-1)(k-2)(k-3); P(K4,3) = 0 (impossible with only 3 colors, since K4 needs 4 mutually distinct colors), and P(K4,4) = 24 (colorings, all 4! ways to assign the 4 distinct colors).

Practice Problems

Difficulty 4/10

Evaluate the chromatic polynomial of the triangle K3 at k = 2 (i.e. is K3 2-colorable, and in how many ways?).

Difficulty 5/10

Using the cycle formula P(C_n,k) = (k-1)^n + (-1)^n(k-1), evaluate P(C3, 3) and check it matches the K3 formula's value at k=3.

Difficulty 7/10

A map with 4 regions is modeled as a graph where each region is a vertex and shared borders are edges, forming exactly K4 (every region borders every other). A cartographer has only 3 ink colors available. Using the chromatic polynomial, can the map be legally colored, and why does this match the Four Color Theorem's spirit?

Quiz

Summary

P(G, k) counts proper colorings of G with at most k colors; it's an honest polynomial in k, first studied by Birkhoff (1912) toward the Four Color Theorem.
Closed forms exist for standard families: P(K_n,k) = k(k-1)...(k-n+1), P(tree,k) = k(k-1)^(n-1), P(C_n,k) = (k-1)^n + (-1)^n(k-1).
The deletion–contraction recurrence P(G,k) = P(G-e,k) - P(G/e,k) computes the polynomial for any graph.
The chromatic number is the smallest k with P(G,k) > 0; P(G,k)=0 means k colors are provably insufficient.

References

WebsiteWikipedia — Chromatic polynomial