School Seminars and Colloquia

Chromatic factorisation and Galois groups of chromatic polynomials

Discrete Structures and Algorithms (Seminar)

by Keri Morgan


Institution: Clayton School of Information Technology, Monash University
Date: Tue 27th April 2010
Time: 2:15 PM
Location: Room 215, Richard Berry Building, The University of Melbourne

Abstract: The chromatic polynomial P(G,k) gives the number of proper
k-colourings of a graph G. This polynomial is also studied in statistical
mechanics where the limit points of the zeros give possible locations of
physical phase transitions.


We say P(G,k) has a chromatic factorisation, if P(G,k)=P(H1,k)P(H2,k)/P(Kr,k)
for some graphs H1 and H2 and some r>=0. Any clique-separable graph,
that is, a graph that can be obtained by identifying an r-clique in H1 with an
r-clique in H2, has a chromatic factorisation. A graph is said to be strongly
non-clique-separable if it is neither clique-separable nor chromatically
equivalent to any clique-separable graph.


We identified strongly non-clique-separable graphs that have chromatic
factorisations. We give an overview of some of our results on these
chromatic factorisations including giving an infinite family of strongly
non-clique-separable graphs that have chromatic factorisations.


We then give a summary of the Galois groups of chromatic polynomials
of degree at most 10. We are interested in identifying the relationships
between graphs that have chromatic polynomials with the same Galois group.
We give some families of graphs that have chromatic polynomials with the
same Galois group.

For More Information: contact: David Wood. email woodd@unimelb.edu.au