Counting colourings of graphs

Every graph theorist knows that the colourings of a graph with a given number of colourings are counted by a certain polynomial, the chromatic polynomial of the graph. My purpose here is to point out that there is more to it than that. I will describe three problems to which polynomials provide the answer, and a fourth to which the answer is not yet known.

I will illustrate with the famous Petersen graph, shown here:

The Petersen graph

Graph colouring

A graph, then, is something like this picture; it has vertices and edges, each edge joining two distinct vertices and not having a direction, and no multiple edges (so each pair of vertices is either joined or not).

A proper colouring of the graph X with q colours is an assignment of the colours to the vertices in such a way that vertices joined by an edge receive different colours.

Theorem There is a polynomial PX with the property that, for any positive integer q, the number of proper colourings of X with q colours is PX(q).

This theorem is usually proved by deletion and contraction. Since I want to talk about the Inclusion-Exclusion Principle, I will give a proof using this principle as an illustration. The Principle of Inclusion and Exclusion, or PIE for short, does the following. If we have a family of subsets of a set, and we know how many elements of the set lie in any prescribed subfamily (and possibly more) of the sets, then we can compute how many elements lie in any prescribed subfamily and no more. The essential part is to count the number of elements lying in none of the sets. This is given by the following statement:

Theorem Let T1,…,Tn be subsets of a set S. For any subset J of {1,…,n}, let TJ be the intersection of the sets Ti for iJi, with T=S. Then the number of elements lying in none of the sets T is given by

ΣJ⊆{1,…,n} (−1)n−|J||TJ|.

The idea of the proof is that we count all the elements of T=S, remove the elements that lie in some set Ti, put back in the ones which have been removed twice, …

Counting proper colourings is a job for this principle. We take the set of all possible colourings, proper or not, of the graph with q colours; there are qn of these, where n is the number of vertices. Now we have to exclude the ones that have bad edges, joining vertices of the same colour. How many colourings have at least a set A of bad edges? To count them, look at the subgraph with edge set A. By assumption, all vertices in a connected component of this graph have the same colour. So, if c(A) is the number of connected components of this subgraph, there are qc(A) such colourings. Then PIE gives the number of colourings with no bad edges as

PX(q) = ΣAE (−1)|EA|qc(A),

which is clearly a polynomial in q. This polynomial is the chromatic polynomial of X.

For the Petersen graph, the chromatic polynomial is

PX(q) = q(q−1)(q−2)×
(q7−12q6+67q5−230q4+529q3−814q2+775q−352).

We see that the least number of colours required for a proper colouring (the smallest q for which this is non-zero) is 3, and the number of proper colourings for q up to 10 is given in the following table:

q 3 4 5 6 7 8 9 10
PX(q) 120 12960 332880 3868080 27767880 144278400 594347040 2055598560

Up to order of colours

From many points of view, it does not matter which colours are assigned to which vertices; only the partition of vertices into colour classes is important. Each colour class is an independent set, a set containing no edges; so we want to count partitions into independent sets.

Before rushing in and dividing the numbers in the preceding table by q!, we have to realise that in the original colouring problem, there is no requirement that every colour actually appears; however, the parts of a partition are required to be non-empty. So first we have to count the colourings in which every colour actually appears.

This is once again a job for PIE. Let S be the set of all colourings with q colours, and for each i let Ti be the set of colourings in which colour i does not appear. We want to count colourings lying in none of the sets Ti. Defining TJ as in PIE, we see that if |J|=qr, then TJ consists of colourings using just r prescribed colours, so has size PX(r). So, by PIE, the number of colourings using q colours, all of which actually appear, is

PX*(q) = Σrq (−1)qr{q choose r}PX(r).

(Note that this is not a polynomial, since it is zero if qn.)

Dividing this number by q!, we obtain the number of partitions into q independent sets. For the Petersen graph, the numbers are

q 3 4 5 6 7 8 9 10
PX*(q)/q! 20 520 2244 2865 1435 315 30 1

Up to symmetry

Now let us return to colourings in the original sense; but perhaps we don’t want to count two colourings as different if they agree up to symmetry of the graph, that is, there is a graph automorphism which takes one to the other. So what we are counting are the orbits of the symmetry group on the set of colourings.

To get the answer it does not suffice simply to divide the number of colourings by the number of symmetries. The answer is given by the Orbit-Counting Lemma:

Theorem The number of orbits of a finite group G acting on a finite set X is obtained by counting, for each element gG, the number of elements of X which are fixed by g, summing these numbers, and dividing the result by |G|.

Given an automorphism g of a graph X, how many q-colourings does it fix? To find the answer, decompose the permutation g of the vertices into cycles; if a colouring is fixed, then vertices in the same cycle must get the same colour. So, if any cycle contains an edge, then the number is zero; otherwise, shrink each cycle to a single vertex and count colourings of the resulting graph (each can be extended uniquely to a colouring of the original graph fixed by g).

The result is a polynomial in q called the orbital chromatic polynomial associated with the graph X and group G, denoted by OPX,G(q), whose value at a positive integer q is the nmber of G-orbits on proper q-colourings of X.

In this formulation, G can be any group of automorphisms of X, but to answer the earlier question, we take it to be the full automorphism group.

To work this out for the Petersen graph, first we have to understand its automorphisms.

A convenient representation of the Petersen graph is as follows. The vertices can be labelled with the 2-element subsets of {1,2,3,4,5}; two vertices are joined if and only if their labels are disjoint. It is clear from this description that the symmetric group S5 acts on the graph, and in fact this is the full automorphism group.

Now it is easy to see that the only automorphisms whose cycles contain no edges are the identity, 2-cycles, and 3-cycles on {1,2,3,4,5}. (For example, the cycle (12,23,34,45,15) of the permutation (1,2,3,4,5) contains an edge from 12 to 34.) Now doing the calculation, we find that the orbital chromatic polynomial is

OPX,G(q) = q(q−1)(q−2)×
(q7−12q6+67q5−220q4+469q3−664q2+595q−252)/120.

The values for 3 to 10 colours are

q 3 4 5 6 7 8 9 10
OPX,G(q) 6 208 3624 36654 248234 1254120 5089392 17449788

Combining?

What if we don’t care about the names of the colours, and also want to count up to symmetry?

The first step of what we did works fine: PIE gives us a formula for the number of orbits on q-colourings in which all the colours are used. The numbers are

q 3 4 5 6 7 8 9 10
OPX,G*(q) 6 184 2644 17910 60690 105840 90720 30240

But we cannot simply divide these numbers by q! to get the number of orbits on partitions. This is because it is possible that a permutation of the parts of a partition can be realised by applying a symmetry, so we would be undercounting. Indeed, the numbers in the table are not all divisible by q!.

I don’t know a mechanical method of finding the number of orbits of G on partitions of X into q independent sets. This would be an interesting research problem. In the case of the Petersen graph, the six orbits with q=3 are indeed all the same if permutations of the colours are allowed, so the first entry in the corresponding table would be 1.

Acyclic orientations

Richard Stanley noticed that, if we substitute −1 into the chromatic polynomial of the graph, we obtain (up to sign) the number of acyclic orientations of the graph, that is, the number of ways of assigning directions to the edges so that no directed cycle is created.

Unfortunately, substituting −1 into the orbital chromatic polynomial doesn’t give the number of orbits of G on acyclic orientations of X; but there is another polynomial, the twisted orbital chromatic polynomial, which does this job. It is calculated in the same way as the chromatic polynomial, but terms corresponding to odd permutations g are given a minus sign, that is, subtracted rather than added.

The twisted orbital chromatic polynomial of the Petersen graph is given by

q(q−1)(q−2)(q−3)×
(q6−9q5+40q4−120q3+229q2−277q+164)/120.

We find that the 16680 acyclic orientations of the Petersen graph fall into 168 orbits under the automorphism group.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems and tagged , , , . Bookmark the permalink.

One Response to Counting colourings of graphs

  1. I finally got round to computing the “missing numbers”, the numbers of colourings with q colours, with q running from 3 to 10, where the names of the colours are not significant and the count is up to symmetry of the graph. (As noted in the post, I don’t know how to calculate this from polynomial data associated with the graph and the group actions, so I listed all the partitions with q parts, filtered out those which are not proper colourings, and then classified them into orbits for the automorphism group. Then numbers for q=3, … 10, are
    1, 10, 30, 36, 20, 7, 1, 1.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s