# 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