Chromatic polynomial

Definition

Let $G$ be a finite graph. For each natural number $k$, let $P(G, k)$ be the number of colourings of $G$ with the set of colours $\{1, \dots, k\}$. There is a unique polynomial $P(G, x)$ whose value at each natural number $k$ is $P(G, k)$. It is the chromatic polynomial of $G$.

Remarks

For the path graph $P_3$, $P(P_3, x) = x(x-1)^2$. For the complete graph, $P(K_n, x) = x(x-1)\cdots(x-n+1)$. For an edge $e$, the deletion–contraction rule says $P(G, x) = P(G - e, x) - P(G / e, x)$. Here $G / e$ merges the two ends of $e$. The chromatic number is the smallest positive integer $k$ with $P(G, k) > 0$.

Explanations

L1 human

The chromatic polynomial counts the proper colourings of a graph with $k$ colours, for each $k$. George David Birkhoff introduced it in 1912 to study the four colour problem.