monash63023.pdf (2.5 MB)

Download file# Algebraic aspects of the chromatic polynomial

thesis

posted on 13.01.2017, 04:08 by Morgan, Kerri Jo-AnneThe 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).