The chromatic polynomial
of an undirected graph G
is the polynomial f(x)
such that f(n)
is the number of different ways to color G
using n colors.
- C4: x4 - 4 x3 + 6 x2 - 3 x
- K3: x3 - 3 x2 + 2 x
- K3,3: x6 - 9 x5 + 36 x4 - 75 x3 + 78 x2 - 31 x
Some basic properties:
- The largest power with a non-zero coefficient is the number of nodes in the graph
- f(x) = P(x) * (x-(k-1)) * ... * (x-1) * x, where k is the chromatic number of the graph.