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:

- C
_{4}: x^{4} - 4 x^{3} + 6 x^{2} - 3 x
- K
_{3}: x^{3} - 3 x^{2} + 2 x
- K
_{3,3}: x^{6} - 9 x^{5} + 36 x^{4} - 75 x^{3} + 78 x^{2} - 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.