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 PG(-1). [Stanley, 1978]

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

  • PG(x) = PG-e(x) - PG|e(x)
  • PG(x) = PG+e(x) + PG|e(x)
where PG(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:

     |    |
     |    |
If we identify along the edge (C,D), we get:
      \   |
       \  |
        \ |
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 PG(x) = PG-e(x) - PG|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:

  • K3,3: x6 - 9x5 + 36x4 - 75x3 + 78x2 - 31x
  • Cube graph: x8 - 12x7 + 66x6 - 214x5 + 441x4 - 572x3 + 423x2 - 133x
  • Petersen graph: x10 - 15x9 + 105x8 - 455x7 + 1353x6 - 2861x5 + 4275x4 - 4305x3 + 2606x2 - 704x

Chromatic polynomials computed with GraphThing, my graph theory software, available free at
Cube graph chromatic polynomial fixed (s/411/441) -- June 2006