chromatic polynomial (idea)

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⁶ - 9x⁵ + 36x⁴ - 75x³ + 78x² - 31x
• Cube graph: x⁸ - 12x⁷ + 66x⁶ - 214x⁵ + 441x⁴ - 572x³ + 423x² - 133x
• Petersen graph: x¹⁰ - 15x⁹ + 105x⁸ - 455x⁷ + 1353x⁶ - 2861x⁵ + 4275x⁴ - 4305x³ + 2606x² - 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