(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 C4), 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 x4-4x3+6x2-3x is the same chromatic polynomial that Hykin's writeup gives for C4, so it's probably right.
With suitable data files, we can also check the chromatic polynomials given in the above writeups for K3:
3
AB
BC
CA
K3,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 x4 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.