Algebraic aspects of the chromatic polynomial

The chromatic polynomial P(G, λ) gives the number of proper colourings of a graph G in at most λ colours. Although there has been considerable interest in the chromatic polynomial, there has been little research into its algebraic theory. This thesis considers some algebraic properties of the chromatic polynomial: factorisation and the Galois groups of chromatic polynomials. If P(G, λ) = P(H1, λ)P(H2, λ)/P(Kr , λ), then G is said to have a chromatic factorisation of order r with chromatic factors H1 and H2. It is known that the chromatic polynomial of any clique-separable graph, that is, a graph containing a separating r-clique, has a chromatic factorisation. Two graphs are said to be chromatically equivalent if they have the same chromatic polynomial. A graph is said to be strongly non-clique-separable if it is not chromatically equivalent to any clique-separable graph. We show that there exist strongly non-clique-separable graphs that have chromatic factorisations and identify all chromatic polynomials of degree ≤ 10 of these graphs. We introduce the notion of a certificate of factorisation which is used to explain these factorisations. We find an upper bound of n^2*2^(n^2/2) for the lengths of these certificates, and much smaller certificates for all chromatic factorisations of graphs of order ≤ 9. We also give an infinite family of strongly non-clique-separable graphs that have chromatic factorisations and a certificate of factorisation for these graphs. We show that every H1 (excluding K3) with χ(H1) ≥ 3, even when H1 contains no triangles, is the chromatic factor of some chromatic factorisation of order 3 and give a certificate of factorisation for this chromatic factorisation. We then consider chromatic equivalence and give a way to find infinitely many pairs of chromatically equivalent graphs where exactly one of the pair is clique-separable. We find the Galois groups of all chromatic polynomials of strongly non-clique-separable graphs of order ≤ 10 and θ-graphs of order ≤ 19. Two graphs are said to be Galois equivalent if their chromatic polynomials have the same Galois group. We identify some operations on graphs that give a graph that is Galois equivalent to the original graph. We give cases where P(G′, λ) = P(G, λ) + P(Q, λ) where G and G′ are Galois equivalent and P(Q, λ) has the trivial Galois group. Although such a G and G′ can easily be found when P(G, λ) and P(G′, λ) have the trivial group, we give two families of graphs that satisfy this expression where the Galois groups are S2 and D(5). The family of graphs that has chromatic polynomials with Galois group D(5) is particularly interesting as most chromatic polynomials of degree ≤ 10 have symmetric Galois groups and occurrences of nonsymmetric groups are quite rare. We give infinite families of Galois equivalent graphs with chromatic polynomials with Galois groups A(3), D(4) and C(4). One of these graphs has the chromatic polynomial of lowest degree with Galois group A(3).