Monash University
monash63023.pdf (2.5 MB)

Algebraic aspects of the chromatic polynomial

Download (2.5 MB)
posted on 2017-01-13, 04:08 authored by Morgan, Kerri Jo-Anne
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).


Campus location


Principal supervisor

Graham Farr

Year of Award


Department, School or Centre

Information Technology (Monash University Clayton)


Doctor of Philosophy

Degree Type



Faculty of Information Technology

Usage metrics

    Faculty of Information Technology Theses


    No categories selected


    Ref. manager