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.
Some examples:
- 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.