combinatoricsgraph theorymath-softwareprogrammingreference-request
Does anyone know if there is any software that can generate graphs and compute their chromatic polynomials?
For example, say I want to generate all simple graphs on 8 vertices with 16 edges with clique number 5 and have their chromatic polynomials computed (or at least know the specific number of proper $\lambda$-colorings for a specific $\lambda$). Is this possible?
Thank you in advance.
You also need some base cases, which can be deduced from the definition of a chromatic polynomial.
The chromatic polynomial for $K_n$ (the complete graph on $n$ vertices) is $k(k-1)\cdots(k-n)$.
The chromatic polynomial for $\overline{K_n}$ (the null graph on $n$ vertices; i.e. no edges) is $k^n$.
The general idea is to delete/contract edges until you are left with only these base cases (or some other case you have already computed).
Here's an example of performing the deletion-contraction method on the graph $K_{1,2}$. At each step, we perform deletion/contraction on the orange edge.
We separately compute
and
.
(I've used different notation to you since I can't draw the graph in the subscript.)
Using the base cases, we know
$=k^3-k^2$,
which we substitute into the first equation to give the chromatic polynomial:
$=(k^3-k^3)-k(k-1)=k(k-1)^2.$
If you want to know the number of ways of $5$-colouring $K_{1,2}$, we simply substitute $5$ into its chromatic polynomial. It turns out there are $80$ ways to $5$-colour $K_{1,2}$.
Note: in addition to the "deletion contraction" relation, there is also an "addition identification" relation which, in some cases, will be significantly faster.
I'm not sure if it's right but here is an example for G:
χ(G) = 3,
ω(G) = 2,
β(G) = 3 and
θ(G) = 3
Best Answer
Actually it will be better to use sage. I had to wait a minute for sage to generate the 1312 graphs with 8 vertices and 16 edges, but it took no time to filter out the 94 graphs with clique number 5, and no time to compute the chromatic polynomials.
The program geng in the nauty package would generate the graphs much more quickly. But you still have to determine clique numbers and chromatic polynomials and I don't think this is part of nauty's skill set - it didn't use to be, but I haven't checked for a while.
Once you're looking at graphs on more than 8 vertices, it would be much better to produce them using geng and then read them into sage. [And it would even better to follow Gordon Royle’s comment!]