Some more properties:

- The coefficient of the second-highest power is always -e, where e is the number of edges in the graph.
- Except for null graphs, the sum of the coefficients is always zero. For null graphs, the sum is, of course, 1.
- The chromatic polynomial for a tree graph on n vertices is x(x-1)
^{n-1}.
- Interestingly, the number of acyclic orientations of a graph is given by P
_{G}(-1). [Stanley, 1978]

The two most useful formulas, though, are the following:

- P
_{G}(x) = P_{G-e}(x) - P_{G|e}(x)
- P
_{G}(x) = P_{G+e}(x) + P_{G|e}(x)

where

*P*_{G}(x) denotes the chromatic polynomial of the

graph G,

*G-e* denotes the

graph G with the edge e removed,

*G+e* denotes the

graph G with the edge e added, and

*G|e* denotes the

graph obtained from G by identifying the two vertices incident to e.

That last one (*G|e*) is probably the most confusing, so I'll explain it in a bit more detail. Say we have a graph G:

A*----*B
| |
| |
D*----*C

If we identify along the edge (C,D), we get:

A*----*B
\ |
\ |
\ |
C*

That is, we "merge" the two vertices C and D into one vertex.

Now it is easy to work out the chromatic polynomial of the original graph. Since we know that P_{G}(x) = P_{G-e}(x) - P_{G|e}(x), we get (in pseudo-mathematical form):

*----* *---* *----*
| | = \ | - | |
| | \ | | |
*----* * * *

This thus reduces our problem to a more simple problem. If we cannot compute the chromatic polynomial for these

graphs, we simply repeat the procedure until we can.

Chromatic polynomials for common graphs:

- K
_{3,3}: x^{6} - 9x^{5} + 36x^{4} - 75x^{3} + 78x^{2} - 31x
- Cube graph: x
^{8} - 12x^{7} + 66x^{6} - 214x^{5} + 441x^{4} - 572x^{3} + 423x^{2} - 133x
- Petersen graph: x
^{10} - 15x^{9} + 105x^{8} - 455x^{7} + 1353x^{6} - 2861x^{5} + 4275x^{4} - 4305x^{3} + 2606x^{2} - 704x

Chromatic polynomials computed with *GraphThing*, my graph theory software, available free at http://graph.seul.org/

Cube graph chromatic polynomial fixed (s/411/441) -- June 2006