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:
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 P_{X} with the property that, for any positive integer q, the number of proper colourings of X with q colours is P_{X}(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 T_{1},…,T_{n} be subsets of a set S. For any subset J of {1,…,n}, let T_{J} be the intersection of the sets T_{i} for i∈Ji, with T_{∅}=S. Then the number of elements lying in none of the sets T is given by
Σ_{J⊆{1,…,n}} (−1)^{n−|J|}|T_{J}|.
The idea of the proof is that we count all the elements of T_{∅}=S, remove the elements that lie in some set T_{i}, 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 q^{n} 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 q^{c(A)} such colourings. Then PIE gives the number of colourings with no bad edges as
P_{X}(q) = Σ_{A⊆E} (−1)^{|E−A|}q^{c(A), }
which is clearly a polynomial in q. This polynomial is the chromatic polynomial of X.
For the Petersen graph, the chromatic polynomial is
P_{X}(q) | = | q(q−1)(q−2)× |
(q^{7}−12q^{6}+67q^{5}−230q^{4}+529q^{3}−814q^{2}+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 |
P_{X}(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 T_{i} be the set of colourings in which colour i does not appear. We want to count colourings lying in none of the sets T_{i}. Defining T_{J} as in PIE, we see that if |J|=q−r, then T_{J} consists of colourings using just r prescribed colours, so has size P_{X}(r). So, by PIE, the number of colourings using q colours, all of which actually appear, is
P_{X}*(q) = Σ_{r≤q} (−1)^{q−r}{q choose r}P_{X}(r).
(Note that this is not a polynomial, since it is zero if q≥n.)
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 |
P_{X}*(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 g∈G, 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 OP_{X,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 S_{5} 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
OP_{X,G}(q) | = | q(q−1)(q−2)× |
(q^{7}−12q^{6}+67q^{5}−220q^{4}+469q^{3}−664q^{2}+595q−252)/120. |
The values for 3 to 10 colours are
q | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
OP_{X,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 |
OP_{X,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)× |
(q^{6}−9q^{5}+40q^{4}−120q^{3}+229q^{2}−277q+164)/120. |
We find that the 16680 acyclic orientations of the Petersen graph fall into 168 orbits under the automorphism group.
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.