chromatic polynomial

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₄: x⁴ - 4 x³ + 6 x² - 3 x
• K₃: x³ - 3 x² + 2 x
• K_3,3: x⁶ - 9 x⁵ + 36 x⁴ - 75 x³ + 78 x² - 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.

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

Computing the chromatic polynomial

(without fancy-schmanzy special-purpose tools like GraphThing, whatever that is, dsx)

The following Perl 5 script will compute the chromatic polynomial of a graph fed to its standard input.

---

c(1,<>); $i--; map {print s'-''?'-':'+',''x s'^1$'',$_,"x^$i" if $i++,$_} @s;
sub c {my($p,$c,@q)=@_; @q or $s[$c]+=$p,return; return if grep {/(.)\1/} @q;
my($l,$r)=split //,shift @q; c($p,$c,@q); map {s/$l/$r/g} @q; c(-$p,--$c,@q)}

---

(Of course, it's possible to write such a program in legible Perl too, but .sig-length scripts that do something useful are much more fun, no?)

To use the program, prepare a data file containing the graph in the following format: name each vertex of your graph with an ASCII symbol (number, letter, whatever.) The first line of your file gives the number of vertices of the graph; each subsequent line of the file should contain a two-character string corresponding to the two ends of an edge. Thus for a square (also known as C₄), whose vertices you have decided to call A to D, you would use a file such as:

4
AB
BC
CD
DA

(Note that it is not necessary to list the character names of the vertices explicitly.) Save the program as chromatic and the data file above as square, then invoke Perl:

bash$ perl chromatic square
-3x^1+6x^2-4x^3+x^4bash$

Okay, the output could be more elegant, but x⁴-4x³+6x²-3x is the same chromatic polynomial that Hykin's writeup gives for C₄, so it's probably right.

With suitable data files, we can also check the chromatic polynomials given in the above writeups for K₃:

3
AB
BC
CA

K_3,3:

6
A1
A2
A3
B1
B2
B3
C1
C2
C3

the cube graph:

8
AB
BC
CD
DA
12
23
34
41
A1
B2
C3
D4

and the Petersen graph:

10
AB
BC
CD
DE
EA
13
35
52
24
41
A1
B2
C3
D4
E5

In fact the script finds a misprint in dsx's writeup: for the cube graph, the coefficient of x⁴ is not 411 but 441.

The program uses the recursive method outlined by dsx, whose running time is exponential in the number of edges. Consequently it's not practical to use it on really big (or even moderately big) graphs. The Petersen graph takes about a quarter of a second on a 3GHz Xeon system, and that's only fifteen edges.

---

Source

I wrote the above program some years ago (back when Perl 5 was the latest thing) as an undergraduate computing project.